B3630 排队顺序这道题，我第一次看到时只花了三十秒就判定它是道排序题，结果用了四十分钟才调过。问题不在算法，而在读题：题目里那句"按某种规则排好队"听起来像是废话，实际上它压缩了三层信息——按什么维度排、主键相等时谁站前面、排完之后输出谁的什么东西。这三层里任何一层理解偏了，样例照样能过，提交就是一片红。这篇就围绕"排队顺序"这个主题，把排序类题目里那些真正决定成败的细节拆开讲：排序键的提取、比较函数的严格弱序、稳定性到底什么时候是必需的、大规模输入的读入优化、以及"排队"退化成逆序对时该怎么处理。适合刚接触算法题、能写出sort但经常在边界上翻车的人看，也适合已经能 AC 但想搞清楚每一步为什么这么做的人。下面按这类排队题最常见的设定来展开，核心框架对同类题是通用的。

1. 读题阶段：把"排队顺序"四个字拆成可执行的约束

1.1 先看数据规模，它决定了你算法的天花板

很多人拿到题的顺序是"先想思路，再看范围"，这个习惯在入门阶段没问题，但在稍微有点规模的题上会要命。正确的顺序是先把数据范围扫一遍，因为范围直接决定你能用什么复杂度。

以排队顺序这类题为例，人数记作 n，如果 n 只有几百到一两千，那 O(n²) 的暴力插入排序、甚至每次重新扫一遍找最小值的写法都能过，代码短、调试快，完全没必要上树状数组。但如果 n 到了 10 万这个量级，O(n²) 就是 10¹⁰ 次操作，稳稳超时，必须压到 O(n log n)。再往上到 10⁶，连sort都可能被卡，这时候要考虑值域计数排序或者基数排序。

除了 n，还要看每个人身上带的那几个属性各自的范围。凡是出现了 10⁹ 以上的数值，先假设它可能参与运算，累加、乘积、差值统统开long long，别等到 WA 了才回头改类型。我看过太多人因为一个int溢出在同一个点提交了七八次。

读题时我习惯在纸上写三行：n 的上限、每个属性的范围、输出要求。这三行写出来，算法的骨架基本就定死了，剩下的只是填肉。

1.2 把自然语言条件翻译成主键、次键和兜底键

排队顺序这类题最有意思的地方在于，它很少只给你一个排序条件。真实描述往往是"按身高从矮到高排，身高相同的按编号从小到大排"，或者"优先级高的先排，优先级相同则先来先服务"。

这种描述本质上是在定义一个多关键字的比较规则。主键是第一个条件（身高），次键是第二个条件（编号），有时候还会出现第三键。翻译的时候要特别注意"相同"这两个字——它是次键出现的唯一信号，读到"相同""并列""若……则"这类词，立刻在脑子里记一笔：这里需要二级比较。

还有一类条件藏得更深，比如"编号小的排在前面"，如果主键是身高，那这句就是次键；但如果主键本身没写清楚，这句反而可能是主键。判断方法是看哪一句单独拿出来就能唯一确定一个顺序。能唯一定序的那句是主键，其余的降级为次键和三级键。

我一般会把这些条件读成一张表，写清楚每一列对应哪个属性、升序还是降序、相等时往哪儿走。

这张表填完，代码几乎是照着抄。真正容易出错的不是填表，而是漏填——很多人在心里过一遍就直接开写，结果漏了"相等时"的处理，测试数据里恰好没有重复值，就侥幸过了，实际上逻辑是漏的。

1.3 输出格式是题面的一部分，不是细节

排完序之后输出什么，这件事被低估的程度堪比"忘了取模"。常见的坑有这几个：输出的是编号还是身高，输出的是原下标还是排序后的位置，元素之间用空格还是换行，末尾要不要留空格。

尤其最后一条，很多在线评测对行尾空格是容忍的，但有些严格比对会判格式错误。稳妥的做法是统一用"第一个元素单独输出，后面每个元素前面先打一个空格"的模式，这样整行末尾永远不会多出空格。

如果题目要求输出两行，比如第一行是人数、第二行是序列，那么在读完 n 之后就要立刻输出第一行，而不是等到最后。这个顺序错了，答案就整体错位，偏偏样例里 n=5 的时候你很难一眼看出来。

2. 比较函数：排序类题目里最容易写错的一行代码

2.1 cmp 必须满足严格弱序，<=是最常见的致命错误

手写比较函数几乎是每个人必经的一关，而return a.x <= b.x;这个写法是踩坑率最高的一行。它看起来和<只差一个等号，实际上会让比较函数不满足严格弱序。

严格弱序听起来很学术，翻译成人话就是三条规矩：任何元素和自己比必须返回假（不可自反）、a 比 b 为真则 b 比 a 必须为假（反对称）、比较结果要能传递。用了<=之后，第一条就被破坏了——cmp(a, a)返回真，意味着"a 排在 a 前面"，这在逻辑上就不成立。

一旦违反，std::sort的行为是未定义的。未定义不是"结果稍微乱一点"，而是可能死循环、可能越界访问、可能在你本地跑得好好的、换个编译器就崩溃。我在不同环境下见过同一个错误写法一次正常输出、一次段错误，排查了半天才发现是这一行。

正确写法只有一句话：比较函数里只写严格小于，相等一律返回假。

struct Person { int id; // 编号 int height; // 身高 }; // 身高升序，身高相同按编号升序 bool cmp(const Person &a, const Person &b) { if (a.height != b.height) return a.height < b.height; return a.id < b.id; }

注意第二个return用的是<而不是<=。当a.height == b.height且a.id == b.id时（也就是两个完全相同的元素），函数返回假，这符合"它们互相之间谁也不排在谁前面"的语义，sort就能正常处理。

2.2 手写 cmp、pair、结构体重载运算符，三条路的取舍

同一个排序需求至少有三种实现方式，选哪个取决于你后面还要不要拿这个结构体干别的事。

第一种是手写 cmp 函数。优点是灵活，任何复杂条件都能塞进去；缺点是要单独写一个函数，参数得多传一层 const 引用，而且容易写错。第二种是把多个关键字打包成pair或tuple，靠标准库自带的字典序比较，一行sort就完事。第三种是在结构体里重载operator<，之后直接sort(v.begin(), v.end())，语义最自然。

pair的坑在于它只支持字典序升序。如果题目要求"身高升序、编号降序"，直接打包就不行了，得用make_pair(h, -id)这种技巧，但-id在 id 可能是 0 的时候会出问题，而且用负数取巧会让代码可读性变差。这种情况下老实写 cmp 反而更清爽。

我个人的习惯是：关键字不超过两个且都是升序，用pair；有降序或者三个以上关键字，用结构体重载；需要临时换排序规则，才写独立的 cmp 函数。

2.3 稳定性到底什么时候是必需的

std::sort是不稳定排序，std::stable_sort是稳定的。区别在于：两个"相等"的元素，稳定排序保证它们保持原始相对顺序，不稳定排序不保证。

什么时候这个区别会真的影响答案？当"相等"的元素在题目眼里其实不等的时候。比如排队顺序题里，如果题面说"身高相同的保持原始输入顺序"，那你用不稳定的sort就错了，必须上stable_sort。

但更常见的处理方式不是换排序函数，而是把原始下标当作最后一个比较键。因为如果两个元素的所有比较键都相等，它们的相对顺序本来就不影响结果的正确性；而如果原始顺序有影响，说明原始下标本身就该是一个比较维度，把它显式加进去，逻辑会更清楚，也不会依赖stable_sort的额外开销。

注意：stable_sort的内部实现通常会额外申请一块 n 大小的临时内存，在内存限制紧张或者 n 特别大的时候，它比sort更容易出现内存相关的问题。能用显式下标解决的就别滥用稳定排序。

3. 输入输出与常数：把超时挡在门外

3.1 读入方式对运行时间的影响比你想的大

一道逻辑完全正确的程序，因为在 10⁶ 个整数上用了默认的cin，跑出 1.8 秒被判超时，这种情况在实际提交里非常普遍。默认的cin和cout为了保证与 C 的stdio同步，会关掉缓冲区优化，每次读写都带着额外开销。

解决办法有三个层次。最省事的是在main开头加两行：

ios::sync_with_stdio(false); cin.tie(nullptr);

第一行关掉与 stdio 的同步，第二行解除cin与cout的绑定（否则每次cin之前都会强制刷新cout）。这两行加上之后，cin的速度能提升数倍，应付 10⁶ 级别的数据足够了。

如果还不行，就改用scanf。scanf没有同步开销，读整数比cin快，但如果要读字符串还是得注意格式符。

再往上就是手写快读，用getchar逐字符解析。这种方式在极端情况下能再快一截，代价是代码变长、可读性下降，而且不支持浮点数这类复杂格式。

inline int readInt() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } return x * f; }

我的建议是：n 在 10⁵ 以内，关同步的cin完全够用；到了 10⁶，先关同步，实测超时再换快读。不要一上来就写快读，那会掩盖你真实的性能判断能力。

3.2 输出环节的两个隐形成本

输出端的坑主要在两个地方。

第一个是endl。它不只是换行，还会强制刷新缓冲区，每次调用都是一次系统调用级别的操作。在循环里用endl输出 10⁵ 行，慢得离谱。换成'\n'就好了，它是纯粹的换行字符，缓冲由系统自己管理。

第二个是拼接方式。把结果逐个cout出来，每个元素都要走一遍流操作；如果先把结果拼成一个字符串再一次性输出，速度会快不少。对于排队题这种"输出一行 n 个数"的场景，可以用ostringstream或者手写字符串拼接。

至于行尾空格，我前面提过"第一个元素单独输出"的模式，这里补一下代码形态：

for (int i = 0; i < n; ++i) { if (i) cout << ' '; cout << ans[i]; } cout << '\n';

这段逻辑简单，但能避免掉绝大多数格式错误。别小看这一个空格的差别，我见过有人因为行尾多了个空格，在同一道题上提交了十几次。

3.3 下标从 0 还是从 1：一个影响调试体验的选择

这个问题看起来是纯风格问题，实际上会实打实地影响你找 bug 的速度。

如果题目输入的编号是从 1 开始的，而你的数组从 0 开始存，那每次引用元素都要在心里做一次-1的转换。这个转换在一百行代码里做几十次，总有一次会漏，而且漏了之后报错位置往往离真正的错误很远。

我的做法是：只要题目里的编号是 1 起的，且这个编号本身要参与比较或输出，我就把数组开成 n+1，下标直接用题目给的值。多花一个int的空间，换来的是"代码里看到的数字和题目里看到的数字完全一致"。

反过来，如果编号只是个读入顺序、不参与任何逻辑，那就用 0 起下标，配合范围for循环，代码更紧凑。

这条经验听起来很琐碎，但在真正的调试现场，减少一次心算就是减少一次出错的机会。

4. 当"排队"不是一次排序：模拟、相邻交换与逆序对

4.1 认清题目到底要的是"排好"还是"排的过程"

前面三节都在讲"排完序输出结果"，但排队顺序这一类题里还有一大分支，问的是排队的过程。典型问法是：每次只能交换相邻的两个人，最少交换多少次才能让队伍变成目标顺序。

这两种问法的解法完全不同。前者是排序，一次sort结束；后者是求逆序对，需要额外的数据结构或者分治。很多人读完题直接写sort，输出的是排好的序列，而题目要的是一个数字，答案自然全错。

判断方法是看输出：输出一个序列，就是排序；输出一个整数，八成是计数类问题。再结合题面里"最少""次数""操作"这类词，基本可以确认是逆序对方向。

还有一种情况是排队过程中有动态插入、有人离开、需要随时查询某个位置是谁。这类问题用排序解决不了，得上链表或者平衡树。但它们通常会有额外提示，比如"操作次数不超过 10⁵"，看到"操作"两个字就该警觉。

4.2 相邻交换的最小次数等于逆序对数量

这个结论值得展开讲，因为它是后面所有优化的基础。

假设目标是把当前序列变成升序。考虑任意一对元素 (i, j)，其中 i < j 但 a[i] > a[j]，这一对就是所谓的逆序对。因为 a[i] 比 a[j] 大却排在前面，它们俩的相对位置最终必须调换。

每次交换相邻的两个元素，最多只能消除一个逆序对——交换 a[k] 和 a[k+1]，只会影响这两个元素与其他元素之间的逆序关系，而这两个元素之间的逆序关系被消除，其余所有元素对的关系不变。

所以最少交换次数至少是逆序对的数量。另一方面，用冒泡排序的思路，每次扫描都把相邻的逆序对交换掉，每交换一次恰好消除一个逆序对，最终一定能把序列排好。下界和上界相等，结论成立。

需要提醒的是，这个结论默认所有元素互不相同。如果存在相等的元素，"逆序对"的定义就要用严格大于，而且在有重复值时，某些交换实际上是"不必要"的，具体要看题目对相等元素的处理规则。做题时如果数据里可能出现重复值，一定要回到题面确认。

4.3 逆序对的三种求法，从暴力到树状数组

理解完原理，落地就有三条路。

暴力法是双重循环，对每个 i 扫一遍 j > i 统计a[i] > a[j]的次数。代码三行，复杂度 O(n²)，n 超过 5000 就危险。

long long cnt = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (a[i] > a[j]) ++cnt;

归并排序法在合并阶段顺便统计。当右半部分的元素被取出时，说明它比左半部分剩下的所有元素都小，此时左半部分剩余的元素个数就是新增的逆序对数。

long long mergeCount(vector<int>& a, vector<int>& tmp, int l, int r) { if (l >= r) return 0; int mid = (l + r) >> 1; long long res = mergeCount(a, tmp, l, mid) + mergeCount(a, tmp, 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++]; res += mid - i + 1; } } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (int t = l; t <= r; ++t) a[t] = tmp[t]; return res; }

树状数组法换个角度：从左往右扫，每读到一个数就查询"已经出现过多少个比它大的数"，然后把它插入。查询比它大的数量，等价于当前位置之前的总数减去小于等于它的数量。

struct BIT { int n; vector<int> t; BIT(int n) : n(n), t(n + 1, 0) {} void add(int i, int v) { for (; i <= n; i += i & -i) t[i] += v; } int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } };

用树状数组之前要离散化，把原始数值映射到 1..n 的排名，否则值域太大数组开不下。

实战里我优先写归并，因为它不依赖离散化，也不用担心值域问题，代码是固定的模板，抄一遍就能用。树状数组的优势在于它可以处理"边插入边查询"的动态场景，这是归并做不到的。

5. 调不出来的时候：三条排查路径和一份复盘清单

5.1 造数据比改代码更有效

WA 之后第一反应是盯着代码找错，这个习惯要改。绝大多数时候，你盯着看是看不出来的，因为你对这段代码有心理预期，大脑会自动补全成你想要的样子。

更有效的做法是造小数据。n = 3 到 5，元素值手动设计，覆盖这几种情况：全升序、全降序、全部相等、只有两个元素不同、最大值在两端。用这几组数据跑一遍你的程序，把中间状态打出来，错误通常立刻现形。

我自己的习惯是写一个随机数据生成器，n 从 1 开始往后涨，每组跑十次。很多边界错误（比如数组没开够、循环条件少了等号）在 n = 1 的时候就暴露了，而题目给的样例往往是 n = 5 起步，正好绕过去。

5.2 对拍：让程序自己告诉你哪组数据错了

对拍的核心思路是：写一份绝对正确但很慢的实现作为标准答案，再写一份你正在调试的实现，用随机数据同时跑，比较输出。

标准答案可以是暴力 O(n²) 版本，它慢但逻辑简单，几乎不会错。随机生成器负责覆盖各种输入规模，然后用脚本循环比对。

#!/bin/bash for ((i = 1; i <= 1000; ++i)); do ./gen $i > in.txt ./brute < in.txt > out1.txt ./mine < in.txt > out2.txt if ! diff -q out1.txt out2.txt > /dev/null; then echo "diff at case $i" cat in.txt break fi done

这段脚本跑完，第一组出问题的数据就会被打出来，直接拿它去单步调试，比盲猜高效得多。生成器里带上$i作为随机种子，可以保证每轮数据不同，出问题的时候还能用同一个种子复现。

对拍的价值不只是找 bug，它还能帮你验证复杂度的直觉。如果暴力版本在 n = 2000 时 0.2 秒，你的实现要 0.5 秒，那这个实现放到 n = 10⁵ 基本没戏，该优化了。

5.3 一份提交前的自查清单

调过几十道同类题之后，我整理了一张提交前必看的清单，卡题的时候逐条过一遍，命中率相当高。

这张表里前三条属于"一次性错误"，犯一次记住一辈子；后四条属于"每次都可能犯"，需要靠流程去卡。我的做法是把它贴在手边的便签上，提交前扫一眼，三秒钟的事，能省下大量重交的时间。

还有一条清单之外的：改代码的时候一次只改一处。同时改三处然后过了，你根本不知道是哪一处起了作用，下次遇到同样的问题还是不会。这个教训我用了很久才真正接受。

关于排队顺序这类题，我最后再分享一个自己的做法：写完sort之后，先不急着提交，手动把样例的排序过程在纸上走一遍，重点看主键相等的那一对元素有没有被正确放到后面。这个动作花不了一分钟，但能拦下大部分比较函数写错的情况。真正让人烦躁的从来不是难题不会做，而是明明会做却在小地方反复翻车。