ZeroJudge E561: Train Swapping

題目敘述

每筆輸入第一行有一個正整數N，接下來會有N筆資料。每筆資料有兩行，第一行有一個正整數M，第二行有M個整數。要求輸出將第二行的數字進行排序時需要swap (交換) 幾次。

範例輸入 #1

3

3

1 3 2

4

4 3 2 1

2

2 1

範例輸出 #1

Optimal train swapping takes 1 swaps.

Optimal train swapping takes 6 swaps.

Optimal train swapping takes 1 swaps.

解題思路

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

解題程式碼如下 (僅供參考)：

#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";
    }
}