1. 这道小题为什么值得反复刷先把这个题目认出来信息学奥赛一本通 1310【例2.2】车厢重组在洛谷上的编号是P1116。很多刚开始刷题的同学会在不同地方反复碰到它因为它同时出现在一本通的排序章节、洛谷的入门题库、某些学校的OJ作业里。题目本身讲的是火车车厢按编号重新排列要求找出最少需要多少次“相邻交换”才能把乱序的车厢排成升序。这道题表面上是个模拟题但实际考察的是排序算法里一个很核心的结论冒泡排序中元素移动的次数恰好等于序列中逆序对的数量。你要是只会照着题意写一个双重循环暴力模拟虽然也能过但“为什么交换次数就是逆序对数”这个底层逻辑没搞明白后面学到归并排序、树状数组、离散化求逆序对的时候还是会卡壳。所以这篇我打算从题目本身出发把三种做法都捋一遍直接模拟冒泡、归并排序求逆序对、树状数组求逆序对。顺便把常见的坑和调试技巧也写进来。适合刚学排序、刚接触一本通题库、或者洛谷刷到这道题但有点似懂非懂的同学。先给个结论方便你心里有数这道题数据范围很小N 10000暴力冒泡完全可以AC但如果你已经会归并排序或者树状数组完全可以拿这题当试验场把更优的做法跑一遍。我的建议是三种都写一遍因为这题就是一扇门推开之后是一整个“逆序对”知识点家族。2. 题意拆解车厢到底怎么重组的2.1 题目原文到底说了什么题目描述大致是这样一列火车有 n 节车厢每节车厢编号从 1 到 n。车厢当前的顺序是乱序的我们希望通过“交换相邻两节车厢”的方式把这列火车调整为编号从小到大排列。问最少需要多少次相邻交换。输入格式第一行一个整数 n第二行 n 个整数表示当前车厢顺序。输出一个整数表示最少交换次数。样例输入是这样的4 4 3 2 1输出是 6。这个样例很经典因为它是完全倒序的四节车厢完全反着排冒泡排序需要交换 3 2 1 6 次。2.2 题目背后的本质相邻交换与逆序对很多人看到“相邻交换”四个字第一反应是模拟冒泡排序过程这当然没错。但更本质的观察是一次相邻交换最多只能消除一个逆序对。反过来想如果序列里存在一个逆序对——也就是说存在 i j 但 a[i] a[j]——那么这两个元素最终在排序完成时它们的相对位置一定会发生对调而相邻交换每执行一次只能改变一对相邻元素的相对次序。所以要让所有逆序对都消除至少需要逆序对数那么多次交换。再想想冒泡排序每轮做的事情从头到尾扫描相邻元素如果逆序就交换。每一轮一定会把当前最大值“冒”到最右边。这个过程每做一次有效交换就恰好消除一个逆序对而且由于冒泡排序只会交换相邻的逆序元素所以它不会“多交换”任何一次。于是冒泡排序的总交换次数就是初始逆序对数量这个值也就是题目要求的最小值。这里我建议你亲手验证一个数字随便写一个排列比如 5 1 4 2 3数一数它的逆序对。5和后面四个数都构成逆序对1没有4和2、3构成两个2没有3没有总数 4 0 2 6。然后用冒泡模拟一遍交换次数必然也是 6。这个规律非常直观而且能帮你记住“求最小相邻交换次数 求逆序对数”这个等价关系。2.3 为什么不是任意交换非得是相邻交换有的同学可能会问如果是任意交换两个位置那最少几次那个问题答案就是 n - 环的数量完全是另一道题。相邻交换的限制本质上把问题从“图论排列分解”拉回到了“排序稳定性”的范畴也让题目的难度立刻降低了一个档次。这也是为什么这道题会被放在“排序”章节而不是“搜索”或“图论”章节的原因。另外补充一点这题虽然叫“车厢重组”但和火车实际调度里的“栈式编组”“驼峰溜放”不是一回事别被题目背景带偏了它就是个纯排序问题。3. 解法一直接模拟冒泡排序先拿满分3.1 模拟思路与代码实现第一种做法最直白用冒泡排序模拟整个过程每交换一次计数器加一最后输出计数器的值。N 最大 10000冒泡排序的 O(N^2) 最坏情况下就是 1 亿次比较C 在评测机上跑完完全没问题Python 稍慢但通常也能过。C 代码#include iostream using namespace std; int a[10005]; int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; int ans 0; for (int i 1; i n; i) { for (int j 1; j n - i; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); ans; } } } cout ans endl; return 0; }这里有个细节外层循环从 1 到 n内层循环到 n - i。每一轮结束后第 n - i 1 个位置已经放好了当前未排序部分的最大值所以内层范围可以逐步缩小。这个写法是从 1 开始索引如果你习惯从 0 开始内层范围就写成 j n - i - 1逻辑完全一样注意别把自己绕晕。Python 版本更短n int(input()) a list(map(int, input().split())) ans 0 for i in range(n): for j in range(n - i - 1): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] ans 1 print(ans)3.2 为什么模拟冒泡一定能得到最优解这不是“猜”出来的而是冒泡排序的天然性质它每次比较相邻元素只在逆序时才交换而一次相邻交换恰好让逆序对数量减 1。排序完成后逆序对为 0总交换次数自然等于初始逆序对数。正因为每次交换都“精准消除”一个逆序对没有任何多余的交换动作所以它达到的交换次数就是理论下界。这个结论用一句话概括就是冒泡排序的交换次数就是最优解。理解这一点比记住“最小交换次数 逆序对数”更有价值因为以后遇到“只能交换相邻元素”的变种题你能快速联想起来。3.3 暴力模拟的风险与取舍一万的数据量用 O(N^2) 确实很稳但如果哪天题目的 N 改成 10^5 甚至 10^6暴力就会超时。所以从学习的角度我不建议你只会这一种写法就收工。更关键的是模拟冒泡求出的“交换次数”虽然正确但它掩盖了“交换次数只是结果逆序对才是本质”这一点导致很多同学换一道题就不会做。我在带新手的时候经常说一句话如果你是靠模拟冒泡过的这题那之后遇到“求逆序对数”的题一定还会再卡一次。因为逆序对这个概念在归并排序、树状数组、CDQ分治等更高级的算法里反复出现早一点接触后面学起来会顺畅很多。4. 解法二归并排序顺便学会一个经典套路4.1 归并排序为什么能数逆序对归并排序的核心思想是“分治”把数组从中间切开分别排序再把两个有序数组合并成一个有序数组。关键发生在合并阶段当右侧数组的某个元素比左侧数组当前元素小的时候说明这个“小元素”要越过左侧数组剩余的所有元素才能到前面去而这些越过的元素个数恰好就是新增的逆序对数。具体来说合并时维护两个指针 i 和 j分别指向左半部分和右半部分。当 a[i] a[j] 时说明右半部分的 a[j] 应该放到左半部分所有从 i 开始的元素前面因此逆序对数需要加上左半部分剩余元素个数也就是 mid - i 1。4.2 归并排序求逆序对的 C 实现#include iostream using namespace std; int a[10005], tmp[10005]; long long ans 0; void mergeSort(int l, int r) { if (l r) return; int mid (l r) / 2; mergeSort(l, mid); mergeSort(mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (a[i] a[j]) { tmp[k] a[i]; } else { tmp[k] a[j]; ans mid - i 1; // 左半部分剩下的都比 a[j] 大 } } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int p l; p r; p) a[p] tmp[p]; } int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; mergeSort(1, n); cout ans endl; return 0; }这里要注意两个点。第一ans 要用 long long虽然本题 n 只有 10000最坏情况逆序对数量是 n * (n - 1) / 2 49995000int 还勉强够用但归并求逆序对是个通用模板万一 N 是 10^5逆序对数量就到 5 * 10^9int 直接爆。写 long long 是最稳妥的习惯。第二合并时当 a[i] a[j]也就是左侧不大于右侧时不产生逆序对这个等号条件必须写对否则就把相等的元素误判成逆序了。4.3 归并排序的时间复杂度与适用场景归并排序的时间复杂度是 O(N log N)空间复杂度是 O(N)因为需要额外一个临时数组。对本题 N 10000 来说这个复杂度绰绰有余对更大数据范围这也是标准解法。适用场景上只要题目是“求逆序对数量”或者“相邻交换排序的最小交换次数”归并排序都能解决。而且归并排序本身是稳定排序这意味着它不会改变相等元素的相对顺序这个性质和求逆序对时“等号不计数”是配套的。4.4 归并排序的代码细节与我踩过的坑归并排序是典型的一写就错、一调就对但初学者往往会栽在一些隐蔽的地方递归边界if (l r) return不要写成 l r虽然结果一样但后者在理解上容易忽略空区间的问题。mid 的计算(l r) / 2这个写法没问题。但如果 l 和 r 都很大用 l (r - l) / 2 更安全不过竞赛里一般用不到。合并完成后的回写不要忘记把临时数组拷回原数组否则后续递归合并时用的还是旧数据。指针 k 的初始值在合并函数里k 要从 l 开始而不是从 0 开始。有些手写习惯的同学喜欢全局临时数组从 0 开始这也没问题但要注意和下标对齐。我在最初学归并排序的时候回写那一步经常漏结果整个数组“莫名其妙”没排序排查很久才发现是临时数组没拷回去。现在我的习惯是写完合并逻辑马上检查三件事临时数组下标是否正确、合并完有没有回写、逆序对计数加的是不是 mid - i 1。三件事都确认了基本不会出问题。5. 解法三树状数组进阶选手的标准姿势5.1 树状数组求逆序对的基本原理树状数组求逆序对是另一种经典解法。思路是把数组元素依次插入树状数组插入某个数 x 之前先查询已经有多少个数比 x 大这个数量就是当前元素和之前元素构成的逆序对数。具体做法是反向扫描从后往前遍历数组每遇到一个数 x就查询树状数组里小于 x 的数的个数这个值就是以当前元素为“逆序对左端”的逆序对数量。或者正向扫描查询大于 x 的个数写法上等价。因为树状数组的索引要求是正整数所以如果数组元素值域很大需要先做离散化把输入数据映射成 1 到 n 的排名。本题车厢编号就是 1 到 n天然就离散好了直接用就行。5.2 树状数组的 C 模板#include iostream #include algorithm using namespace std; int n; int a[10005]; int c[10005]; int lowbit(int x) { return x (-x); } void add(int i, int v) { while (i n) { c[i] v; i lowbit(i); } } int sum(int i) { int res 0; while (i 0) { res c[i]; i - lowbit(i); } return res; } int main() { cin n; for (int i 1; i n; i) cin a[i]; long long ans 0; for (int i n; i 1; i--) { ans sum(a[i] - 1); add(a[i], 1); } cout ans endl; return 0; }这段代码中sum(a[i] - 1) 查询的是当前已经出现过的、编号小于 a[i] 的车厢个数这些车厢在原始序列中位于 a[i] 的右边但编号更小所以它们和 a[i] 构成逆序对。从右往左扫描保证我们只统计了右侧元素不会漏也不会重。5.3 离散化当数据不是 1~N 的时候怎么办假如题目把车厢编号换成任意正整数甚至负数比如 [100, 200, 50]树状数组就不能直接开了因为下标范围可能很大。这时候需要离散化把原数组复制一份排序去重然后用二分查找把每个元素替换成它在排序数组中的排名。排名是从 1 开始的连续整数正好作为树状数组下标。离散化代码vectorint all(a 1, a n 1); sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); for (int i 1; i n; i) { a[i] lower_bound(all.begin(), all.end(), a[i]) - all.begin() 1; }这里 lower_bound 是二分查找返回第一个不小于 a[i] 的位置因为 all 里去重了所以这个位置就是排名。加 1 是因为 vector 下标从 0 开始而树状数组下标我们习惯从 1 开始。我见过不少同学在离散化时忘了去重结果 equal 元素被当成两个不同排名逆序对数量就算错了。实际上相等元素不构成逆序对离散化时一定要保留去重这一步。lower_bound 返回同一个位置恰好保证了相等元素的排名相同。5.4 树状数组和归并排序怎么选两种算法时间复杂度都是 O(N log N)常数上树状数组通常更小代码也更短。但归并排序的思维更通用能推广到求“顺序对”“非严格逆序对”等多种变体。树状数组的优势是支持动态修改和查询如果题目要求边插入边查询、多次询问树状数组往往更灵活。对这道题来说数据范围很小三种做法都能过所以选哪种主要看你目前掌握到哪个阶段。我的建议是如果这是你第一次接触逆序对老老实实把归并排序写通如果你已经会用树状数组那就顺手在本题上验证一下模板把两种思路都打通。6. 常见报错与调试技巧实录6.1 运行结果不对从样例开始排查很多同学写完代码直接提交WA 了之后一脸懵。我的排查习惯是先跑样例输入肉眼比对中间结果。算逆序对的题最好自己在草稿纸上写出每一轮的逆序对增量再和程序输出对照。比如对样例 4 3 2 1逆序对正确增量应该是 3 2 1 6。如果你归并排序的输出是 3那大概率是在合并时漏掉了“左半部分剩余元素”的计数只加了一个 1。遇到这种情况在合并循环里打印 ans 的变化就能很快定位。6.2 递归爆栈怎么办归并排序的递归深度是 log N正常 N 不会爆栈。但如果你在递归里开了巨大的局部数组比如 int temp[100005] 写在函数内部栈空间可能不够。建议把临时数组声明为全局变量或 static这不仅是习惯问题也关系到程序能不能在评测机上安全运行。树状数组不用递归没有这个问题但要注意树状数组大小至少是 N如果你开了 N却访问了下标 N在 add 里 while (i n) 会正常退出。如果你开小了数组越界可能带来难以排查的错误。6.3 提交显示“答案错误”但本地没问题多半是整数溢出本题 n 最大 10000最大逆序对数约 5 * 10^7int 能存下但如果测试数据范围扩大或者你直接套用模板去做别的题int 溢出会非常隐蔽。我的经验是只要涉及逆序对计数一律用 long long不要省。你不差这 4 个字节但 WA 一次的成本远高于这几 Byte。6.4 洛谷提交的小细节洛谷的题目编号是 P1116输入输出用标准输入输出流即可。如果你在本地用文件读写提交前记得删掉 freopen否则评测机会直接判错。这类问题几乎每个新手都遇到过一遍我见过有同学本地测试明明是对的提交秒 WA结果就是 freopen 忘删了。另外洛谷对 C 的默认标准是 C14如果你用了 C17 的新特性比如结构化绑定可能会导致编译错误。本题不需要这些特性普通写法就没问题。7. 写在最后的一点经验这道车厢重组我前前后后带过不少学生写发现一个很有意思的现象直接模拟冒泡的代码一般写得很快但过两周再问“为什么交换次数等于逆序对数”多半答不上来而用归并排序写过的虽然代码调试时间更长但印象会深刻得多后面遇到更复杂的逆序对问题迁移起来也顺滑很多。所以如果你现在还只会暴力我特别建议多花一小时把归并排序和树状数组都写一遍。不要觉得这题简单就跳过算法学习的路上很多“简单题”其实藏着一整片知识森林。这道题就是那扇森林的入口刷过去之后你会发现后面还有“离散化树状数组求逆序对”“归并排序求重要逆序对”“二维逆序对”等一系列相关问题在等你。最后分享一个小技巧写这类题先在题号旁边注明核心考点比如在 P1116 旁边写一行“相邻交换最小次数 逆序对数量”之后再刷题时翻到这一页一眼就能唤醒记忆。这个习惯我保持了很多年对复习特别管用。