b373. [福州19中]车厢重组

---

解法一、模擬

🔹 氣泡排序

遍歷 nums[]
如果 nums[i] > nums[i+1] 表示順序反了
所以 swap(nums[i], nums[i+1]) 以確保小的數字在左邊

遍歷一次就可以確定 nums[nums.size()-1] 是最大的數字
遍歷 n 次就可以確定 nums[] 的最後 n 個數是最大的數字

這樣的遍歷總共需要進行 nums.size()-1 次
(確定了 nums[] 的最後 nums.size()-1 個數後，就不需要檢查 nums[0] 了)

題目求 nums[] 使用 氣泡排序法 排序總共需要交換幾次

4, 3, 2, 1

以 範例測資 舉例
對 4, 3, 2, 1 排序（紅字代表交換）

1. 3, 4, 2, 1
2. 3, 2, 4, 1
3. 3, 2, 1, 4
4. 2, 3, 1, 4
5. 2, 1, 3, 4
6. 1, 2, 3, 4

總共交換 6 次

✅ 完整代碼

評分結果(參考) ： AC (3ms, 348KB)

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

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, cnt = 0;
    cin >> n;

    vector<int> nums(n);
    for(int& num : nums) cin >> num;

    for(int i=0; i<n-1; i++){
        for(int j=0; j<n-1; j++){
            if(nums[j] > nums[j+1]){
                swap(nums[j], nums[j+1]);
                cnt++;
            }
        }
    }
    cout << cnt;
    
    return 0;
}