CPE 一顆星選集 49 道必考題
題目連結:https://zerojudge.tw/ShowProblem?problemid=e561
內容
給定一數列,一次只能交換相鄰兩數,問最少需交換幾次才能完成排序(由小到大)。
輸入第一列 N 代表測資數,每組測資第一列有一整數 L (0 <= L <= 50) 代表數列長度,接著為數列。
範例輸入
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.
想法
分別計算每個數的後面有多少個數比它小,最後加總起來即為所求。
程式碼
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr) using namespace std;
int main(){ fastio; int N, L, mp[51], change; cin >> N; while(N--){ cin >> L; change = 0; for(int i = 0; i < L; ++i) cin >> mp[i]; for(int i = 0; i < L - 1; ++i){ for(int j = i + 1; j < L; ++j){ if(mp[i] > mp[j]) ++change; } } cout << "Optimal train swapping takes " << change << " swaps.\n"; } }
|