ZeroJudge A362: 搬雕像

王先生是一位收藏家，他收集了非常多有名的雕像。某天，為了美觀，他想要將收藏台上的雕像按照某種方式重新擺放，由於雕像都有一定的重量，所以他決定雇用一位年輕人，小明，來幫忙搬雕像。

王先生收藏的雕像目前是以隨機的方式放在收藏台上，收藏台的位置由左至右成一列排開，編號依序為 1, 2,…, N，每個收藏台上放置一個雕像，而收藏台 i (1 ≤ i ≤ N)上目前放的雕像編號為 Si，其高度為 hi 公分，重量為 wi 公斤。王先生要求小明依照下列方式去重新擺放雕像：

  1. 搬動過程中，一次只能搬一個雕像，而每個收藏台可暫時放置 0
    個、1 個、或多個雕像。
  2. 完成重新擺放之後需符合下列條件：
    • 每個收藏台上放置一個雕像。
    • 雕像必須根據高度，由低至高從最左邊的收藏台開始依序放置。
    • 若任二雕像的高度相同時，則重量輕的雕像放置在左邊。
    • 若任二雕像高度和重量都相同時，則依照原先雕像的左右相對順序來放置，也就是說原先在左邊的雕像必須放置在左邊。

為了節省搬運的距離，小明希望你替他寫出一個程式，根據上述方式將雕像重新擺放在收藏台上且搬動的總距離為最短。本題假設任二相鄰收藏台的距離為 1 公尺。

範例測資

範例輸入範例輸出
EOF 輸入，第一行有一個整數 N，1 ≤ N ≤ 10000，代表收藏台的個數。接下來的 N 行，每行有兩個整數以空白隔開，其中第 i 行(1 ≤ i ≤ N)為目前放在收藏台i 上雕像 Si 的高度 hi (單位為公分) 和重量 wi (單位為公斤)，hi 和 wi 都介於 1 和 65536 之間。輸出一個整數，代表搬動雕像所需的最短總距離(單位為公尺)。
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
ZeroJudge A362 範例測資

解題思路

可以使用 Struct 來將所有資料存在一個資料型態中。

因為一個展示台上可以擺放多個雕像，所以先使用題目講的規則將雕像進行排列。完成排序之後將每個雕像原本的位置和目前位置的相差加到答案中，答案其實就是每個雕像和原先位置的差總和。

範例程式碼－ZeroJudge A362: 搬雕像

#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
標籤

相關文章

發佈留言