ZeroJudge 解題筆記：b373. [福州19中]车厢重组

作者：王一哲
日期：2025年7月22日


ZeroJudge 題目連結：b373. [福州19中]车厢重组

解題想法

這題實際上就是考氣泡排序法的交互次數。據說第二筆測資車廂編號的資料有問題，可能被空行分隔，不是只有一行，用 Python 解題時，需要加上一些濾掉空行的工具。

Python 程式碼

使用時間約為 0.2 s，記憶體約為 3.3 MB，通過測試。

import sys

n = int(sys.stdin.readline())  # n 節車廂
arr = []  # 車廂編號
for line in sys.stdin:  # 讀取多行測資
    if not line.strip(): continue  # 如果是空行，讀下一行
    arr += list(map(int, line.split()))  # 如果不是空行，轉成串列接到 arr
### 氣泡排序法，找交換次數 ###
cnt = 0
for i in range(n-1):
    for j in range(i+1, n):
        if arr[i] > arr[j]:
            arr[i], arr[j] = arr[j], arr[i]
            cnt += 1
sys.stdout.write(f"{cnt:d}\n")

C++ 程式碼

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

#include <cstdio>
using namespace std;

int main() {
    int n; scanf("%d", &n);  // n 節車廂
    int arr[n];  // 車廂編號
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    // 氣泡排序法，找交換次數
    int cnt = 0;
    for(int i=0; i<n-1; i++) {
        for(int j=i+1; j<n; j++) {
            if (arr[i] > arr[j]) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                cnt++;
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}