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 把自然语言条件翻译成主键、次键和兜底键排队顺序这类题最有意思的地方在于它很少只给你一个排序条件。真实描述往往是按身高从矮到高排身高相同的按编号从小到大排或者优先级高的先排优先级相同则先来先服务。这种描述本质上是在定义一个多关键字的比较规则。主键是第一个条件身高次键是第二个条件编号有时候还会出现第三键。翻译的时候要特别注意相同这两个字——它是次键出现的唯一信号读到相同并列若……则这类词立刻在脑子里记一笔这里需要二级比较。还有一类条件藏得更深比如编号小的排在前面如果主键是身高那这句就是次键但如果主键本身没写清楚这句反而可能是主键。判断方法是看哪一句单独拿出来就能唯一确定一个顺序。能唯一定序的那句是主键其余的降级为次键和三级键。我一般会把这些条件读成一张表写清楚每一列对应哪个属性、升序还是降序、相等时往哪儿走。描述中的原文提取出的角色处理方式按身高从矮到高主键升序比较身高相同的按编号次键升序比较编号也相同的保持原顺序稳定性要求用 stable_sort 或把原下标当第三键输出排好队的人的编号输出内容输出属性而不是下标这张表填完代码几乎是照着抄。真正容易出错的不是填表而是漏填——很多人在心里过一遍就直接开写结果漏了相等时的处理测试数据里恰好没有重复值就侥幸过了实际上逻辑是漏的。1.3 输出格式是题面的一部分不是细节排完序之后输出什么这件事被低估的程度堪比忘了取模。常见的坑有这几个输出的是编号还是身高输出的是原下标还是排序后的位置元素之间用空格还是换行末尾要不要留空格。尤其最后一条很多在线评测对行尾空格是容忍的但有些严格比对会判格式错误。稳妥的做法是统一用第一个元素单独输出后面每个元素前面先打一个空格的模式这样整行末尾永远不会多出空格。如果题目要求输出两行比如第一行是人数、第二行是序列那么在读完 n 之后就要立刻输出第一行而不是等到最后。这个顺序错了答案就整体错位偏偏样例里 n5 的时候你很难一眼看出来。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())语义最自然。方式写法量出错概率适用场景手写 cmp 函数中中条件复杂、需要动态切换规则pair / tuple 打包少低关键字都是升序、数量不超过三个结构体重载少低结构体在多个地方复用、需要默认排序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 起的且这个编号本身要参与比较或输出我就把数组开成 n1下标直接用题目给的值。多花一个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[k1]只会影响这两个元素与其他元素之间的逆序关系而这两个元素之间的逆序关系被消除其余所有元素对的关系不变。所以最少交换次数至少是逆序对的数量。另一方面用冒泡排序的思路每次扫描都把相邻的逆序对交换掉每交换一次恰好消除一个逆序对最终一定能把序列排好。下界和上界相等结论成立。需要提醒的是这个结论默认所有元素互不相同。如果存在相等的元素逆序对的定义就要用严格大于而且在有重复值时某些交换实际上是不必要的具体要看题目对相等元素的处理规则。做题时如果数据里可能出现重复值一定要回到题面确认。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(vectorint a, vectorint 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; vectorint 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 的排名否则值域太大数组开不下。方法时间复杂度空间复杂度代码量推荐场景暴力O(n²)O(1)极少n ≤ 5000 或对拍用的标准程序归并O(n log n)O(n)中通用不依赖值域树状数组O(n log n)O(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 一份提交前的自查清单调过几十道同类题之后我整理了一张提交前必看的清单卡题的时候逐条过一遍命中率相当高。检查项常见问题影响数据类型累加变量用了 int大数溢出结果变负比较函数出现或严格弱序被破坏运行结果不可预期数组大小按 n 开而不是 n1下标从 1 起时越界读入方式大输入用了默认 cin超时输出格式行尾空格、换行数不对格式错误边界情况n 1、全部相等逻辑分支没覆盖稳定性该保持原序却用了 sort答案顺序错误这张表里前三条属于一次性错误犯一次记住一辈子后四条属于每次都可能犯需要靠流程去卡。我的做法是把它贴在手边的便签上提交前扫一眼三秒钟的事能省下大量重交的时间。还有一条清单之外的改代码的时候一次只改一处。同时改三处然后过了你根本不知道是哪一处起了作用下次遇到同样的问题还是不会。这个教训我用了很久才真正接受。关于排队顺序这类题我最后再分享一个自己的做法写完sort之后先不急着提交手动把样例的排序过程在纸上走一遍重点看主键相等的那一对元素有没有被正确放到后面。这个动作花不了一分钟但能拦下大部分比较函数写错的情况。真正让人烦躁的从来不是难题不会做而是明明会做却在小地方反复翻车。 
长河君 · 2026/11/2 7:34:17 · 阅读 1.2k 排队顺序题拆解：严格弱序、稳定性与逆序对
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 把自然语言条件翻译成主键、次键和兜底键排队顺序这类题最有意思的地方在于它很少只给你一个排序条件。真实描述往往是按身高从矮到高排身高相同的按编号从小到大排或者优先级高的先排优先级相同则先来先服务。这种描述本质上是在定义一个多关键字的比较规则。主键是第一个条件身高次键是第二个条件编号有时候还会出现第三键。翻译的时候要特别注意相同这两个字——它是次键出现的唯一信号读到相同并列若……则这类词立刻在脑子里记一笔这里需要二级比较。还有一类条件藏得更深比如编号小的排在前面如果主键是身高那这句就是次键但如果主键本身没写清楚这句反而可能是主键。判断方法是看哪一句单独拿出来就能唯一确定一个顺序。能唯一定序的那句是主键其余的降级为次键和三级键。我一般会把这些条件读成一张表写清楚每一列对应哪个属性、升序还是降序、相等时往哪儿走。描述中的原文提取出的角色处理方式按身高从矮到高主键升序比较身高相同的按编号次键升序比较编号也相同的保持原顺序稳定性要求用 stable_sort 或把原下标当第三键输出排好队的人的编号输出内容输出属性而不是下标这张表填完代码几乎是照着抄。真正容易出错的不是填表而是漏填——很多人在心里过一遍就直接开写结果漏了相等时的处理测试数据里恰好没有重复值就侥幸过了实际上逻辑是漏的。1.3 输出格式是题面的一部分不是细节排完序之后输出什么这件事被低估的程度堪比忘了取模。常见的坑有这几个输出的是编号还是身高输出的是原下标还是排序后的位置元素之间用空格还是换行末尾要不要留空格。尤其最后一条很多在线评测对行尾空格是容忍的但有些严格比对会判格式错误。稳妥的做法是统一用第一个元素单独输出后面每个元素前面先打一个空格的模式这样整行末尾永远不会多出空格。如果题目要求输出两行比如第一行是人数、第二行是序列那么在读完 n 之后就要立刻输出第一行而不是等到最后。这个顺序错了答案就整体错位偏偏样例里 n5 的时候你很难一眼看出来。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())语义最自然。方式写法量出错概率适用场景手写 cmp 函数中中条件复杂、需要动态切换规则pair / tuple 打包少低关键字都是升序、数量不超过三个结构体重载少低结构体在多个地方复用、需要默认排序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 起的且这个编号本身要参与比较或输出我就把数组开成 n1下标直接用题目给的值。多花一个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[k1]只会影响这两个元素与其他元素之间的逆序关系而这两个元素之间的逆序关系被消除其余所有元素对的关系不变。所以最少交换次数至少是逆序对的数量。另一方面用冒泡排序的思路每次扫描都把相邻的逆序对交换掉每交换一次恰好消除一个逆序对最终一定能把序列排好。下界和上界相等结论成立。需要提醒的是这个结论默认所有元素互不相同。如果存在相等的元素逆序对的定义就要用严格大于而且在有重复值时某些交换实际上是不必要的具体要看题目对相等元素的处理规则。做题时如果数据里可能出现重复值一定要回到题面确认。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(vectorint a, vectorint 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; vectorint 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 的排名否则值域太大数组开不下。方法时间复杂度空间复杂度代码量推荐场景暴力O(n²)O(1)极少n ≤ 5000 或对拍用的标准程序归并O(n log n)O(n)中通用不依赖值域树状数组O(n log n)O(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 一份提交前的自查清单调过几十道同类题之后我整理了一张提交前必看的清单卡题的时候逐条过一遍命中率相当高。检查项常见问题影响数据类型累加变量用了 int大数溢出结果变负比较函数出现或严格弱序被破坏运行结果不可预期数组大小按 n 开而不是 n1下标从 1 起时越界读入方式大输入用了默认 cin超时输出格式行尾空格、换行数不对格式错误边界情况n 1、全部相等逻辑分支没覆盖稳定性该保持原序却用了 sort答案顺序错误这张表里前三条属于一次性错误犯一次记住一辈子后四条属于每次都可能犯需要靠流程去卡。我的做法是把它贴在手边的便签上提交前扫一眼三秒钟的事能省下大量重交的时间。还有一条清单之外的改代码的时候一次只改一处。同时改三处然后过了你根本不知道是哪一处起了作用下次遇到同样的问题还是不会。这个教训我用了很久才真正接受。关于排队顺序这类题我最后再分享一个自己的做法写完sort之后先不急着提交手动把样例的排序过程在纸上走一遍重点看主键相等的那一对元素有没有被正确放到后面。这个动作花不了一分钟但能拦下大部分比较函数写错的情况。真正让人烦躁的从来不是难题不会做而是明明会做却在小地方反复翻车。