One day, to enhance the aesthetics of his collection, Mr. Wang decided to rearrange the statues on the display stand. Given that the statues had a considerable weight, he hired a young man named Xiao Ming to assist in moving them.
Mr. Wang’s collection of statues is currently placed randomly on display stands, arranged in a row from left to right, numbered sequentially as 1, 2, …, N. Each display stand holds one statue, and the statue currently on stand i (1 ≤ i ≤ N) has the identification number Si, a height of hi centimeters, and a weight of wi kilograms. Mr. Wang has instructed Xiao Ming to rearrange the statues according to the following criteria:
- During the moving process, only one statue can be moved at a time, and each display stand can temporarily hold 0, 1, or more statues.
- After the rearrangement is completed, the following conditions must be met:
- Each display stand must hold exactly one statue.
- The statues must be placed from left to right on the display stands, arranged in ascending order of height starting from the leftmost stand.
- If the heights of any two statues are the same, the lighter statue should be placed on the left.
- If two statues have the same height and weight, they should be placed in their original relative order, meaning that the statue that was originally on the left must remain on the left.
To minimize the distance of transportation, Xiao Ming wants you to write a program that rearranges the statues on display stands according to the aforementioned rules while ensuring that the total movement distance is the shortest. In this problem, the distance between any two adjacent display stands is assumed to be 1 meter.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| EOF input, where the first line contains an integer N (1 ≤ N ≤ 10,000), representing the number of display stands. The following N lines each contain two integers separated by a space, where the i -th line (1 ≤ i ≤ N ) represents the height h_i (in centimeters) and weight w_i (in kilograms) of the statue S_i currently placed on display stand i . Both h_i and w_i are in the range of 1 to 65,536. | Output an integer representing the shortest total distance (in meters) required to move the statues. |
| 5 5 20 10 25 78 40 25 25 5 15 8 5 15 3 5 9 13 13 20 24 30 40 50 9 12 5 15 | 8 18 |
Thought Process
You can use a struct to store all the data in a single data type.
Since multiple statues can be placed on a display stand, first, arrange the statues according to the rules mentioned in the problem. After completing the sorting, calculate the difference between each statue’s original position and its current position, and add this to the total answer. The final answer is essentially the sum of the differences for each statue from its original position.
Sample Code－ZeroJudge A362: Moving Statues
#include <iostream>
#include <math.h>
using namespace std;
struct statue {
int ID;
int h;
int w;
};
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
while (cin >> N) {
statue arr[20000] = {};
for (int i = 0; i<N; i++) {
statue temp;
temp.ID = i;
cin >> temp.h;
cin >> temp.w;
arr[i] = temp;
}
for (int i = 0; i<N; i++) {
for (int j = 0; j<N-1; j++) {
if (arr[j].h > arr[j+1].h) {
swap(arr[j], arr[j+1]);
}
if (arr[j].h == arr[j+1].h) {
if (arr[j].w > arr[j+1].w) {
swap(arr[j], arr[j+1]);
}
}
if (arr[j].h == arr[j+1].h && arr[j].w == arr[j+1].w) {
if (arr[j].ID > arr[j+1].ID) {
swap(arr[j], arr[j+1]);
}
}
}
}
int ans = 0;
for (int i = 0; i<N; i++) {
ans += abs(i - arr[i].ID);
}
cout << ans << endl;
}
}
//ZeroJudge A362
//Dr. SeanXD