车厢重组

题意

有一列车厢，每次操作只能交换相邻两节车厢。问最少交换多少次，才能把车厢编号排成从小到大。

思路

一次相邻交换最多只能消掉一对顺序错误的车厢。

如果 cars[i] > cars[j] 且 i < j，这两节车厢就是一对逆序对。最终升序排列时，较小的那节一定要越过较大的那节，所以每一对逆序对都至少需要一次相邻交换。

反过来，冒泡排序每交换一次相邻逆序元素，就恰好减少一个逆序对，直到逆序对数量变成 0。因此最少操作次数就是初始逆序对数量。

本题 n <= 1000，直接两层循环统计即可。

Python 知识

sys.stdin.buffer.read().split() 适合这种“全是整数，换行不重要”的输入。
list(map(int, ...)) 一次把所有 token 转成整数，后面按下标切出数组。
双层 for 循环直接枚举所有 i < j 的数对，写法和 C++ 中的两层循环一一对应。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13import sys

data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
cars = data[1:1 + n]

answer = 0
for i in range(n):
    for j in range(i + 1, n):
        if cars[i] > cars[j]:
            answer += 1

print(answer)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int n;
int a[MAXN]; // 车厢编号

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 冒泡排序的思想：统计逆序对数量
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) // 前面的数比后面大，构成逆序对
                ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

复杂度

时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ 。

总结

看到“只能相邻交换，问最少交换次数”，要立刻联想到逆序对。这里数据范围很小，不需要树状数组或归并排序。

目录

题意

思路

Python 知识

代码

复杂度

总结