ZeroJudge E561: Train Swapping

同題：UVa 00299 – Train Swapping

在老舊的火車站，您也許會遇到少數僅存的”車箱置換員”。
“車箱置換員”是鐵路部門的員工，主要工作就是重新排列火車車廂。
一旦以最佳順序排列了車廂，所有火車司機要做的就是將車廂逐一卸下即可。
“車箱置換員”源自在鐵路橋附近的車站中執行此任務的第一人。
這座橋並不會垂直打開，而是繞著河中央的一根支柱旋轉。將橋旋轉90度後，船隻就能向左或向右駛過。
第一位”車箱置換員”發現，這座橋最多可以在其上運行兩個車廂，通過將橋旋轉180度，車廂就能切換位置。
(缺點是車廂面向相反的方向，但是火車車廂可以以任何一種方式移動，所以沒差）。
現在幾乎所有的”車箱置換員”都已經淘汰了，鐵路公司希望將其操作自動化。
你的任務就是寫一個程式，該程式要計算最少需要交換幾次兩個相鄰車廂，才能將所有車廂依序排好。

範例測資

範例輸入範例輸出
輸入的第一行包含一個整數 N，N 代表測資數量。
每組測資的第一行包含一個整數 L (0 ≤ L ≤ 50)，L 代表火車的長度。
第二行包含數字 1 到 L 的排列，表示火車車廂的當前順序。
需要將火車車廂依照編號 1 到 L 的順序排好。		對於每組測資，請輸出：
「Optimal train swapping takes S swaps.」，S 代表最少交換次數，可忽略單數不加 s 之文法規則。
3
3
1 3 2
4
4 3 2 1
2
2 1		Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

解題思路

可以使用 Bubble Sort (氣泡排序法)，每次進行 Swap 的時候就將答案的變數+1，最後輸出Swap的次數。

範例程式碼－ZeroJudge E561: Train Swapping

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        int len;
        cin >> len;
        vector<int>num;
        for (int j = 0; j<len; j++)
        {
            int tmp;
            cin >> tmp;
            num.push_back(tmp);
        }
        int ans = 0;
        for (int j = 0; j<len; j++)
        {
            for (int k = 0; k<len-1; k++)
            {
                if (num[k] > num[k+1])
                {
                    swap(num[k], num[k+1]);
                    ans++;
                }
            }
        }
        cout << "Optimal train swapping takes " << ans << " swaps.\n";
    }
}

//ZeroJudge E561
//Dr. SeanXD
標籤

相關文章

發佈留言