“书架还原”这道题我是出了蓝桥杯省赛考场才敢回头细细复盘。今年C语言组的题目整体风格偏思维很多同学出考场直呼被“书架”整蒙了——名字听起来像一道模拟题实际是一道换了皮的逆序对计数问题。如果你正在刷蓝桥杯真题这道题值得反复做三遍它既考数据结构的敏感度也考你对排序类算法原理的理解深度。下面我按参赛选手回忆的题面把完整思路、两份可以直接提交的C语言代码以及我在考场上和赛后对拍时踩过的坑都写出来。这篇文章适合正在备赛蓝桥杯C组的同学也适合所有想彻底弄懂“逆序对”这个常考模型的人。1. 题目到底在讲什么先看懂“书架还原”1.1 题目背景与题面还原蓝桥杯省赛的题目有个特点喜欢把一个经典算法模型包装成一个生活场景。“书架还原”也不例外。按参加过第十六届省赛的同学复述题面大意是这样的小蓝的书架上有 n 本书从左到右依次排开。每本书上有一个编号原本编号应该是 1, 2, 3, ..., n按从左到右从小到大摆放。结果被家里的小朋友打乱了顺序现在从左到右看编号变成了一个乱序的排列。小蓝每次只能做一步操作把相邻两本书交换位置。他想要把书架恢复成 1, 2, 3, ..., n 的顺序问最少需要多少次相邻交换。数据范围比较有杀伤力n 最大可以达到 500000。也就是说你写一个 O(n^2) 的暴力做法哪怕只测满数据的一半程序也会跑到天荒地老。部分分可能会给 n 很小的测试点但想要拿高分必须上 O(n log n) 级别的算法。这里先说明一下蓝桥杯不同组别C组、研究生组等题面文字可能略有差异有的版本会说“书的高度各不相同按高度从矮到高还原”有的版本直接说“按编号排序”。但剥掉这层壳数学模型完全一样给一个 1~n 的排列只能交换相邻元素求排成升序的最小交换次数。1.2 样例推演从乱序到有序到底要几步我在赛场上拿到这种题第一件事不是急着写代码而是手动推一个小样例把答案算出来看能不能发现规律。假设 n 3初始排列是3 1 2。第一步交换第1本和第2本得到 1 3 2此时用了1次。第二步交换第2本和第3本得到 1 2 3此时用了2次。所以答案是 2。再试一个稍微大点的n 4初始排列是 4 3 2 1。这就是完全倒序。细想一下如果把 4 从最左边一路换到最右边需要 3 次接着把 3 换到倒数第二个位置需要 2 次把 2 换到倒数第三个位置需要 1 次最后 1 已经在最左边。总次数是 3 2 1 6。如果我们定义“逆序对”为一对下标 (i, j)满足 i j 且 a[i] a[j]那么 4 3 2 1 里的逆序对数量是 C(4,2) 6。这和 6 次完全一致。而第一个样例 3 1 2 里的逆序对是 (3,1) 和 (3,2)正好也是 2 个。到这里基本可以猜最少交换次数 逆序对数量。这个猜想能不能证明下一节细说。1.3 核心考点拆解题目背后想考什么这道题表面是“模拟书架整理过程”实际考点非常集中主要有四个第一能否从“相邻交换”联想到“逆序对”。这是最关键的一步考场上看不出这一点后面全白搭。第二能否写出 O(n log n) 的逆序对计数算法。具体来说就是归并排序或者树状数组两条路都能走通。第三结果的数据范围。n 500000 时理论上最多的逆序对数量是 500000 * 499999 / 2约等于 1.25e11这个值早就超出 int 的表示范围了必须用 long long。这也是蓝桥杯很喜欢埋的坑。第四输入输出效率。数据量达到 5e5 这个级别如果还抱着 cin/cout 或者 scanf 的默认缓冲不优化哪怕算法复杂度合格也有可能在数据量大的测试点上吃超时的亏。“书架还原”不是孤例蓝桥杯历年很喜欢这种包装题把逆序对、前缀和、差分、并查集这些经典模型装进一个生活场景里。你能透过现象看到本质这道题就赢了。2. 从暴力到规律为什么相邻交换次数等于逆序对数2.1 暴力模拟为什么必然超时看到相邻交换很多人第一反应是直接模拟从第一个位置开始找到当前应该是哪本书然后一路交换过去。这就是冒泡排序的思路。每次找到最小的那个数把它“冒泡”到正确位置同时记录交换次数。代码写起来很简单逻辑也不会错。问题是复杂度。最坏情况下比如数列完全倒序冒泡排序需要执行 n(n-1)/2 次比较和交换。n 500000 时这个数大约是 1.25e11。就算机器一秒钟能执行 1 亿次操作也要 1000 多秒跑一个测试点就超时到天际了。蓝桥杯的时限一般是 1 到 3 秒所以暴力只能拿前几个小数据点的分。有些同学会想我用“每次都把最小的书冒泡到最前面”这算不算优化形式上确实比无脑冒泡少做一些无用比较但在完全倒序的排列里所需交换次数仍然是 n(n-1)/2你一次交换都没法省。因为每个逆序对都需要一次相邻交换来消灭这是客观下界任何模拟都绕不过去。2.2 一个关键观察一次交换只改变一对元素的相对顺序咱们换个角度看问题。最终目标是从乱序排列变成升序排列。假设初始排列中存在一对书本 (i, j)i 在 j 的左边但是 a[i] 比 a[j] 大也就是一个“逆序对”。在最终状态i 号的正确位置应该比 j 号靠左也就是说这一对元素从左到右的相对顺序必须改变。可我们的操作只能交换相邻两本书。一次相邻交换本质上是让两个紧挨着的元素互换位置只改变这一对元素的相对顺序不会影响其他任何一对元素的相对顺序。所以每一次操作最多只能“修复”一个逆序对。要把所有逆序对都修复成“正序对”至少要执行“逆序对数量”这么多次交换。这个下界是严格的。2.3 逆序对最小交换次数的本质有了下界还要证明这个下界能达到。如果严格按照冒泡排序的流程来操作从左往右扫描每当发现相邻两个元素左边比右边大就交换它们。这样的交换一定减少一个逆序对而且不会产生新的逆序对对冒泡排序稍加分析可以知道交换相邻逆序元素恰好让这一对的顺序恢复其他元素相对顺序不变。继续这样操作下去直到没有相邻逆序对存在此时整个序列必然升序。这个过程执行的交换次数正好等于初始逆序对数量。于是结论非常干净最小相邻交换次数 逆序对数量。逆序对的定义再明确一下对于数组 a[1..n]逆序对是指所有下标对 (i, j)满足 1 i j n并且 a[i] a[j]。注意题目里书的编号如果不重复直接按编号比较即可。如果题面改成“高度各不相同但编号随意”那需要先把高度离散化成 1~n 的编号再求逆序对。2.4 数据规模与算法选型既然问题变成了“求逆序对数量”下一步就是选算法。O(n^2) 肯定不行O(n log n) 是标准答案。实现方式主流有两种归并排序和树状数组。归并排序的思路比较直观合并两个有序数组时顺手统计逆序对不需要额外的离散化步骤代码量也不大对C语言选手非常友好。树状数组的思路更有“数据结构感”核心是利用前缀和统计比当前元素小的个数但需要先对数值做离散化处理或者保证编号范围与 n 同量级。从蓝桥杯C组的实战角度我更推荐归并排序写法。原因后面细说简单讲就是不容易写错不需要离散化出考场后对拍调试也方便。但树状数组解法也值得掌握因为很多变种题比如统计每个位置前面的逆序贡献用树状数组改起来更灵活。两种我都给出完整代码和解释。3. 解法一归并排序求逆序对推荐写法3.1 归并排序回顾归并排序是分治思想的经典实现。把一个数组从中间分成两半分别递归排序然后把两个有序数组合并成一个整体有序的数组。合并过程需要借助一个临时数组把两个有序序列中的较小者依次放入临时数组。以 C 语言实现核心是三个部分递归函数 merge_sort(l, r) 处理区间递归出口是 l r区间里只有一个元素天然有序合并阶段用双指针 i 和 j 分别指向左右两个有序区间的开头比较后把较小的放入 tmp 数组最后把 tmp 复制回原数组 a。归并排序时间复杂度 O(n log n)空间复杂度 O(n)而且它是稳定排序。稳定这个性质在做逆序对计数时非常有用。3.2 合并过程中如何顺手统计答案归并排序能统计逆序对关键是下面这个事实当合并左右两个已经有序的区间时左区间里的元素下标都小于右区间里的元素。也就是说左区间任意元素在原始数组里的位置都在右区间任意元素的前面。假设当前指针 i 指向左区间j 指向右区间。如果 a[i] a[j]那么把 a[i] 放入 tmpi 右移这时没有产生逆序对。但如果 a[i] a[j]说明左区间从 i 到 mid 的所有元素都比 a[j] 大而且它们在原数组中都在 a[j] 所在位置的左边。也就是说(a[i], a[j])、(a[i1], a[j])、...、(a[mid], a[j]) 这 (mid - i 1) 对元素全部构成逆序对。答案累加 mid - i 1然后正常把 a[j] 放入 tmp。用等号的情况一定要处理对当 a[i] a[j] 时放左边元素只有严格大于时才统计逆序对。这样既保证稳定性又不会把相等的元素误判成逆序对。书架上的书编号各不相同但如果你以后遇到含重复值的数组求逆序对这个细节就是生死线。3.3 完整C语言实现下面是我整理好的一份可以直接提交的 C 语言代码。变量名尽量用有含义的单词方便考场阅读和检查。#include stdio.h #define MAXN 500005 int a[MAXN], tmp[MAXN]; long long ans; void merge_sort(int l, int r) { if (l r) return; int mid (l r) 1; merge_sort(l, mid); merge_sort(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 { ans (long long)(mid - i 1); tmp[k] 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; scanf(%d, n); for (int i 1; i n; i) { scanf(%d, a[i]); } ans 0; merge_sort(1, n); printf(%lld\n, ans); return 0; }这份代码在绝大多数评测环境下可以直接跑通。注意 ans 声明成了 long long累加时还显式做了 (long long) 转换防止乘法溢出后隐式转成 int。很多同学在赛场上就栽在这个地方后面我会专门讲。3.4 代码逐行讲解与复杂度分析我把自己在考场上写代码时脑子里过的关键点列一下。递归函数里先求出 mid注意 mid (l r) 1 和 l (r - l) / 2 是等价的前边那个写法位运算更快一点但如果你不习惯写成普通除法也行蓝桥杯不会因为这点常数卡你。合并循环是整个算法的灵魂。两个有序区间开始合并时只要左边当前数小于等于右边当前数就直接放左边一旦左边当前数大于右边当前数说明右边这个数比左边剩下的所有数都小于是把左边剩余数量计入答案。这个“剩余数量”是 mid - i 1千万别写成了 mid - i多一次少一次结果都不对。最后一步把 tmp 复制回 a 时区间是 l 到 r不是 1 到 n。写错的话递归返回上一层时数据就乱了逆序对计数自然全是错的。时间复杂度上每一层递归总共处理 n 个元素递归深度约 log n 层总操作量 n log n。n 500000 时大概是 500000 * 19约 950 万次核心操作一秒内跑完毫无压力。空间上 tmp 数组需要 O(n) 的额外空间5e5 个 int 大约是 2MB堆栈空间也够用。我个人在实战中非常喜欢归并排序求逆序对的写法因为它的思路和代码是一体的你只要记得“合并时左边大的数出现一次就累加对数”这段代码基本不会写错。相比之下树状数组的细节更多一些虽然有它的优势但考场上求稳的话归并排序是C语言选手的最优选。4. 解法二树状数组求逆序对另一种思路4.1 树状数组与离散化树状数组Binary Indexed Tree是另一种非常经典的计数工具它支持单点修改和前缀和查询复杂度都是 O(log n)。用它求逆序对的思路如下从右往左遍历原始数组。维护一个树状数组 cc[x] 表示数值 x 已经出现的次数。当遍历到元素 a[i] 时我已经把 a[i] 右边的所有元素都插入了树状数组。此时查询一下小于 a[i] 的数有多少个也就是 query(a[i] - 1)这些数在原数组中位于 i 的右边却比 a[i] 小正好构成逆序对。累加答案后再把 a[i] 插入树状数组。如果 a[i] 的值本来就限定在 1~n那么树状数组可以直接开 MAXN 大小不需要离散化。但蓝桥杯有时候把“书的编号”换成“书的高度”高度可以是任意整数范围可能很大这时得先排序做离散化把原始值映射成 1~n 的序号保证树状数组下标不会越界同时保持原有的大小关系不变。4.2 核心代码实现先给出不带离散化的写法适用于编号刚好是 1~n 的情况#include stdio.h #define MAXN 500005 int c[MAXN], a[MAXN]; long long ans; int lowbit(int x) { return x (-x); } void add(int idx, int val) { while (idx MAXN) { c[idx] val; idx lowbit(idx); } } int query(int idx) { int res 0; while (idx 0) { res c[idx]; idx - lowbit(idx); } return res; } int main() { int n; scanf(%d, n); for (int i 1; i n; i) { scanf(%d, a[i]); } ans 0; for (int i n; i 1; i--) { ans query(a[i] - 1); add(a[i], 1); } printf(%lld\n, ans); return 0; }如果需要离散化可以这样处理// 先把原始值存到 b 数组升序排序并去重 // 然后对每个 a[i]通过二分查找得到映射后的排名 // 排名值就是树状数组的下标离散化的主要代码逻辑是排序加去重我用一个简单写法说明for (int i 1; i n; i) { scanf(%d, a[i]); b[i] a[i]; } qsort(b 1, n, sizeof(int), cmp); int len unique(b 1, b n 1) - (b 1); for (int i 1; i n; i) { int rank lower_bound(b 1, b len 1, a[i]) - b; a[i] rank; }实际比赛里更稳妥的做法是手写二分查找对应排名因为 C 标准库的 lower_bound 不是 C 的默认函数需要自己实现。4.3 两种解法对比与选型建议归并排序和树状数组都能在 O(n log n) 时间内解决逆序对放到蓝桥杯里都能拿到满分。但它们在实现细节、适用场景上有明显差别我整理了一个表方便你按需求选对比维度归并排序法树状数组法代码量较短约 30 行略长需要实现 lowbit/add/query是否需要离散化不需要编号范围大时需要易错点合并时累加数量、tmp 回写范围循环边界、离散化映射关系扩展灵活性只能处理逆序对计数容易扩展出区间统计、动态维护考场推荐度高中如果你只是单纯应付这道“书架还原”我的建议是死磕归并排序写法。但如果你后续要刷更多涉及动态区间统计的题比如“每次修改一个元素后问逆序对变化”树状数组这套思路会让你更游刃有余。反正两种写法我都推过一遍建议你两个都敲一遍互相印证结果会比只看不练牢固得多。5. 蓝桥杯实战这些坑我替你踩过了5.1 最大的坑ans 忘用 long long这个坑真的每年都有大量人踩。n 500000 时完全倒序排列会有大约 1250 亿个逆序对而 int 最大只能存大约 21 亿。如果你用 int 存答案程序输出会变成一个莫名其妙的负数或者被截断的数字直接 WA。所以定义答案变量时一定要写成 long long ans输出格式用 %lld。在归并排序的合并分支里ans mid - i 1 这段代码理论上右边是 int 运算累加到 long long 时会有一次隐式转换。为了防止某些编译器在极端情况下因为类型提升问题产生溢出我习惯写成 ans (long long)(mid - i 1)养成这个习惯能帮你少掉好几次分。5.2 输入输出性能别让 scanf 拖垮你蓝桥杯的输入规模常常