299 Train Swapping

題目連結

題目敘述

在一個老舊的火車站裡，你可能還會遇到最後幾位「列車調度員」。他們的工作就是將火車的車廂按照正確順序重新排列，方便列車司機在各個車站卸下對應的車廂

現在鐵路公司想要自動化這個操作。他們需要一個程式，計算出將一列車廂排列成由小到大順序時，最少需要交換多少次相鄰車廂

輸入說明

• 第一行是一個整數 N，代表有 N 組測試資料
• 每組測試資料包含兩行：
  • 第一行是一個整數 L，代表車廂數量（0 ≤ L ≤ 50）
  • 第二行有 L 個整數，為 1~L 的一組排列，表示目前車廂的順序

輸出說明

對於每組測試資料，請輸出一行：

Optimal train swapping takes S swaps.

其中 S 為將這組車廂排序成 1 到 L 所需的最少「相鄰兩車廂交換」次數

解題思路

1. 題目要求：計算把車廂序列用相鄰交換（Bubble Sort 的 swap 操作），排序為升序（1, 2, ... L）所需的最少交換次數
2. 做法：用 氣泡排序（Bubble Sort） 的想法，每次把最大的數字慢慢「冒泡」到右邊，同時計算每次交換的次數即可
3. 實作重點：
   • 每兩個相鄰的車廂，如果前面的比後面的還大，就交換並把計數器+1
   • 外層和內層雙迴圈，直到整個序列完成排序
   • 輸出對應的次數即可

程式碼

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int L;
        cin >> L;
        vector<int> vc(L);
        for (int i = 0; i < L; i++) cin >> vc[i];
        int cnt = 0;
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < L - i - 1; j++) {
                if (vc[j] > vc[j + 1]) {
                    swap(vc[j], vc[j + 1]);
                    cnt++;
                }
            }
        }
        cout << "Optimal train swapping takes " << cnt << " swaps." << endl;
    }
    return 0;
}