ZeroJudge 解題筆記：a539. 10327 - Flip Sort

作者：王一哲
日期：2026年1月10日


ZeroJudge 題目連結：a539. 10327 - Flip Sort

解題想法

看起來像是考氣泡排序，但是不能直接跑氣泡排序並計算交換次數，這樣會很慢。從最後一個數字往前找，計算這個數字之前有幾個比較大的數字，將數量相加就是答案。

Python 程式碼

使用時間約為 38 ms，記憶體約為 3.2 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    n = int(lines[idx])
    idx += 1
    arr = list(map(int, lines[idx].split()))
    idx += 1
    cnt = 0
    for i in range(n-1, 0, -1):
        for j in range(i-1, -1, -1):
            if arr[i] < arr[j]:
                cnt += 1
    result.append(f"Minimum exchange operations : {cnt:d}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 3 ms，記憶體約為 36 kB，通過測試。

#include <cstdio>

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        int arr[n], cnt = 0;
        for(int i=0; i<n; i++) scanf("%d", &arr[i]);
        for(int i=n-1; i>0; i--) {
            for(int j=i-1; j>=0; j--) {
                if (arr[i] < arr[j]) cnt++;
            }
        }
        printf("Minimum exchange operations : %d\n", cnt);
    }
    return 0;
}