299 Train Swapping

題目連結

題目敘述

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

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

輸入說明

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

輸出說明

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

Optimal train swapping takes S swaps.

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

解題思路

題目要求：計算把車廂序列用相鄰交換（Bubble Sort 的 swap 操作），排序為升序（1, 2, ... L）所需的最少交換次數
做法：用 氣泡排序（Bubble Sort） 的想法，每次把最大的數字慢慢「冒泡」到右邊，同時計算每次交換的次數即可
實作重點：
- 每兩個相鄰的車廂，如果前面的比後面的還大，就交換並把計數器+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;
}