P4640 车厢重组（基础）

解题思路

这道题的核心是「逆序对」思想：只要还有「前面的车厢号码比后面的大」，车厢就没排好，就需要转一次桥让它们交换。最少旋转次数正好等于逆序对的总数。

**第一步，读懂题意。**有 n 节车厢排成一排，桥每次旋转 180 度能让相邻两节车厢交换位置。问把车厢按号码从小到大排好，最少要转几次桥。

第二步，认识逆序对。「前面的数比后面的数大」的一对车厢，就叫一个逆序对。比如样例 4 3 2 1：拿第 1 节车厢 4 和后面的 3、2、1 比较，形成 3 个逆序对；再拿 3 和后面的 2、1 比较，又形成 2 个；最后 2 和 1 形成 1 个，加起来一共 6 个，所以答案是 6。

**第三步，想明白为什么等于逆序对数量。**每一个逆序对都至少需要交换一次才能消除，而每一次相邻交换正好消灭一个逆序对。所以最少旋转次数就等于逆序对的总数。这也解释了为什么我们不需要真的去模拟桥的旋转过程。

**第四步，用两重循环统计。**车厢总数最大是 1000，用两重循环把每一对车厢都比较一遍：外层循环枚举前面的车厢，内层循环枚举它后面的车厢，只要前面的大于后面的，就说明这一对需要交换，答案加一。

**第五步，注意用 long long。**车厢数最多 1000 时，逆序对最多接近 50 万，用 long long 存答案更保险，防止溢出。

**第六步，确认边界。**如果车厢已经从小到大排好，逆序对是 0 个，一次桥都不用转，答案输出 0 即可。

参考代码

// 计算把车厢交换成升序所需要的最少旋转次数
#include <iostream>
using namespace std;

int main() {
    int n; // 车厢总数
    cin >> n; // 读入车厢总数
    int car[1000]; // 保存车厢号
    for (int i = 0; i < n; i++) { // 依次读入每节车厢
        cin >> car[i]; // 读入车厢号
    }
    long long count = 0; // 记录逆序对数量，也就是最少旋转次数
    for (int i = 0; i < n; i++) { // 枚举前面的车厢
        for (int j = i + 1; j < n; j++) { // 枚举它后面的车厢
            if (car[i] > car[j]) { // 前面的号码更大，需要交换一次
                count++; // 累加一次相邻交换
            }
        }
    }
    cout << count << '\n'; // 输出最少旋转次数
    return 0; // 程序结束
}

复杂度分析

程序用两重循环枚举所有的车厢对：外层循环有 n 次，内层循环平均也有 n 次，所以时间复杂度是 O(n²)。当 n=1000 时，大约只需要计算 100 万次比较，运行非常快。程序只用了一个整型数组保存车厢号，所以空间复杂度是 O(n)。