洛谷：P1116：车厢重组

发布于 4th Apr 2025

题目

这道题不应该完全采用模拟的算法，而是应该在思考过程中，想到两点：一个是排序，一个是分治——而分治自然会导向递归。

而核心点就是“逆序对”。逆序对的定义是：如果一个序列中，存在这样的情况：两个元素的位置分别在ih和j，且\(i\lt j, a[i]\gt a[j]\)；也就是说，按照常规的排序规则，小的元素（a[j]）出现在了一个大的元素（a[i]）之后。

为什么要关注逆序对呢？因为按照题目的描述，每次进行一次“调度”，一定可以减少一个逆序对。有多少个逆序对，就需要多少次“调度”。

于是，问题退化到：一个长度为N的序列中，有多少逆序对呢？

如果我们用常规的遍历手段，那么时间复杂度会是\(O(N^2)\)，不合算——也不知道是否会超时。

回想排序中的归并排序，其中用到了分治的手段，而分治+归并排序的时间复杂度一般为\(O(nlogn)\)，大大缩短了运行时间。

我们用图表来演示一下样例数据（4个数字，输入顺序是4 3 2 1）的处理过程¹：

flowchart TD A["[4 3 2 1]"]--> B["[4 3]"] A-->C["[2 1]"] C-->D["[2]"] C-->E["[1]"] B-->F["[4]"] B-->G["[3]"]

合并4和3：发现\(4\gt 3\)，所以构成逆序对（逆序对数量=1）。合并后成为[3 4]。
合并2和1：同样的情况，发现\(2\gt 1\)，所以构成逆序对（逆序对数量=1）。合并后成为[1 2]。
合并3 4和1 2。因为\(3\gt 1\)，构成逆序对，而且，因为3 4是排好序的，3后面的元素和1同样构成逆序对。逆序对数量=2。再看\(3\gt 2\)，同样构成逆序对，而且出于同样的原因，还要增加2个逆序对。总共是4个逆序对。

这4个逆序对，跨越了目前的分界点；而之前的两个没有跨越，属于区间内的逆序对。

这里涉及到另一个核心公式：\(某个数跨区域的逆序对=(mid-i+1)\)。

其中，mid是现在的分界点，i是左区间的当前索引。这个公式体现了上文提到的：左边已经排好序后，任意一个a[i]如果大于a[j]，那么从i到mid间的所有值都会大于右边，都构成逆序对。

当然，归并排序需要有一个临时的数组方便给将元素搬来搬去。这个这里不展开，直接看代码40-49行（搬迁到临时数组）以及51-55行（搬回待排序数组）即可。

Solution

本题关键是想通，题目中描述的过程就是“每次消除一个逆序对”的过程。然后进一步想到用归并、分治的方法来降低时间复杂度。

作为讲解分治、归并的入门题目，本题的难度适中，是很好的练手题目。