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