ZeroJudge N415: Sculpture

The museum's exhibition hall has N statues, placed at positions 1, 2, ..., N. The weight of the statue placed at position i is known as Wi. The administrator wants to sort them according to their weights: If there are two adjacent statues, namely at positions i and i+1, and Wi > Wi+1, the administrator will use a machine to exchange the positions of the two statues. This action will consume Wi + Wi+1 units of electricity.

The administrator will repeat the aforementioned exchange action until all the statues are sorted in ascending order by weight.

For example, let's consider N = 3 statues with different weights, (W1, W2, W3) = (5, 7, 4). Firstly, exchange the statues at positions 2 and 3, which costs 7 + 4 = 11 units of electricity. At this point, (W1, W2, W3) = (5, 4, 7). Then, exchange the statues at positions 1 and 2, which cost 5 + 4 = 9 units of electricity. Now, (W1, W2, W3) = (4, 5, 7). After sorting, the machine used a total of 11 + 9 = 20 units of electricity.

To assist the administrator, let's calculate how many units of electricity are required to complete the sorting of the statues.

Sample Inputs/Outputs

Thought Process

In this problem, using Bubble Sort to sort and calculate would exceed the time limit. Therefore, Merge Sort should be used. Additionally, the variables in this problem need to be declared as long long int.

When receiving the data, declare a global vector vector num, and store the received data in this vector.

Certainly! You can implement Merge Sort recursively and name the recursive function "merge". The return type of the recursive function should be vector. Even though the problem only requires calculating electricity, sorting is still needed, hence the need for a return value.

The recursive function takes two positive integers, l and r, representing the left and right boundaries, respectively. The array is split in half before sorting. Firstly, it checks if (l >= r), indicating that the array has been reduced to only one element. In this case, it declares a temporary vector tmp, pushes the single element into it with tmp.push_back(num[l]), and returns tmp.

If the array still needs to be split, declare an integer m = (l+r)/2, representing the midpoint between the current boundaries. Then, declare two vectors vector, named left and right, representing the array split in half. Set left = murge(l, m) and right = murge(m+1, r). This will recursively call the function again, starting with vectors containing only one element each.

Next, declare an integer lsum to represent the sum of the data in the left array. This will be used in calculating the answer later. You can calculate lsum using a for loop.

First, declare two integers l_index and r_index, both initialized to 0. These will be used to track the order of elements when merging left and right. Next, run a for loop for left.size() + right.size() iterations since we need to sort and place the elements from left and right into a new vector final. The main idea is to compare elements from left and right and place the smaller one into the final vector first. You can refer to the example below:

From the example above, we can see that "2" is compared with "3" first. Since "2" is smaller, it is placed into the final vector. Then, "5" is compared with "3", and "3" is placed into the final vector. This process continues until all elements are placed into the final vector.

Before placing elements into the final vector, we need to check if l_index has reached left.size(), indicating that all elements from the left array have been placed into the final vector. Additionally, we need to check if r_index has reached right.size(), indicating that we should not place any more elements from the right array into the final vector. The accurate condition for this check would be: if (l_index == left.size() || (r_index != right.size() && right[r_index] < left[l_index])). If we are taking elements from the left array to place into the final vector, there's no need to compare or sort. However, if we are taking elements from the right array, it indicates that there was an exchange of positions, which requires electricity. The above condition is for placing elements from the right array into the final vector.

If there's an exchange of positions, then we need to calculate how much electricity is spent. Firstly, we need to determine how many positions to the left the current number needs to move, which is essentially left.size() - l_index, indicating how many numbers are left in the left array. Then, we need to determine which numbers are passed over when moving to the left, and this requires using the previously declared "lsum" since lsum is the sum of all numbers in the left array. The formula for calculating electricity spent will be (positions to move left) * (current number) + lsum. Finally, remember to increment r_index so that the next iteration of the for loop will examine the next number in the right array.

If the data in 'left' is to be stored in 'final', 'lsum' should be decremented by 'left[l_index]', so that when calculating power, it does not double-count the data that has already been put into 'final'. Also, remember to increment 'l_index'.

After the last for loop finishes, you should return the final vector. In the main program, you can declare a vectortmp = murge(0, N-1), and then output the result ans.

Sample Code－ZeroJudge N415: Sculpture

#include <iostream>
#include <vector>
using namespace std;

vector<long long int>num;
long long int ans = 0;

vector<long long int> murge(const long long int l, const long long int r) {
    if (l >= r) {
        vector<long long int>tmp;
        tmp.push_back(num[l]);
        return tmp;
    }
    const long long int m = (l+r)/2;
    const vector<long long int>left = murge(l, m), right = murge(m+1, r);
    vector<long long int>final;
    long long int lsum = 0, l_index = 0, r_index = 0;
    for (const long long int i : left) lsum += i;
    for (int i = 0; i<left.size()+right.size(); i++) {
        if (l_index == left.size() || (r_index != right.size() && right[r_index] < left[l_index])) {
            ans += (right[r_index]*(left.size()-l_index)) + lsum;
            final.push_back(right[r_index]);
            r_index++;
            continue;
        }
        final.push_back(left[l_index]);
        lsum -= left[l_index];
        l_index++;
    }
    return final;
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    long long int N;
    cin >> N;
    for (long long int i = 0; i<N; i++)
    {
        long long int tmp;
        cin >> tmp;
        num.push_back(tmp);
    }
    vector<long long int>v = murge(0, N-1);
    cout << ans << "\n";
}

//ZeroJudge N415
//Dr. SeanXD