洛谷P1309瑞士轮：归并排序优化实战与C++实现

1. 从一道竞赛题看排序算法的实战选择

"瑞士轮"这个赛制名词，看比赛的人都不陌生——每轮比赛结束后，成绩相近的选手重新配对，赢的往上走，输的往下掉，最终决出排名。洛谷上的P1309这道题，就是把这个赛制搬到了算法竞赛里，要求模拟整个比赛过程并输出最终排名。很多人第一次拿到这道题，脑子里蹦出来的第一个念头就是：每轮比赛完排一次序，多简单。然后兴冲冲地写了个sort，提交，TLE。再优化一下，用stable_sort，还是TLE。最后老老实实学归并排序，才把这道题啃下来。

这道题的核心关键词是归并排序和C++，但它真正考验的，是你对"有序序列合并"这个操作的理解深度。题目本身不复杂，但数据规模摆在那里——选手数量可以到十万级别，比赛轮数也不少，每轮都做一次全量排序，时间复杂度直接爆炸。所以这道题本质上是一道排序优化题，它逼着你去思考：比赛前后，序列的"有序性"到底发生了什么变化？能不能利用这个变化，把每轮排序的代价从O(n log n)降到O(n)？

这篇文章适合两类人看：一类是正在刷洛谷、准备竞赛的选手，想搞明白这道题为什么不能用sort硬怼；另一类是对归并排序只有理论印象、没真正在实战中用过的人，想看看这个"分治"算法在具体问题里是怎么落地的。我会从题目理解、暴力解法的瓶颈、归并排序的适配逻辑、代码实现细节、以及实际调试中容易踩的坑这几个角度，把这道题彻底拆开讲清楚。你不需要有很强的算法基础，但至少得知道什么是数组、什么是排序，剩下的交给我。

2. 瑞士轮赛制的规则拆解与数据建模

2.1 比赛流程的精确理解

先把题目规则捋清楚。有2n名选手，初始时每人有一个实力值和一个初始分数。比赛进行r轮，每轮按照当前分数从高到低排序，然后相邻两人配对比赛——第1名打第2名，第3名打第4名，以此类推。实力值高的那位获胜，获胜者分数加1，失败者分数不变。每轮结束后重新排序，再进行下一轮。最终输出所有选手按分数降序、分数相同按编号升序的排名。

这里有个容易忽略的细节：排序的稳定性要求。题目要求分数相同时按编号升序排列，这意味着你的排序必须是稳定的，或者说你需要自定义比较规则。很多人用sort的时候忘了写二级比较条件，导致分数相同的选手顺序乱掉，答案直接错。这不是算法复杂度的问题，是审题的问题，但每年都有大量人栽在这里。

另一个细节是配对方式。每轮比赛前，选手是按当前分数排好序的，然后第1和第2打，第3和第4打，不是随机配对，也不是首尾配对。这个规则决定了比赛结果对序列有序性的影响方式，也是后面优化算法的关键切入点。

2.2 数据规模与复杂度约束

题目中n的范围通常到10^5，r的范围到50左右。这意味着总选手数是2×10^5，每轮比赛有n场。如果每轮都用sort排序，单次排序是O(2n log 2n)，总共r轮，总复杂度是O(r × 2n log 2n)。代入数字：50 × 2×10^5 × log(2×10^5) ≈ 50 × 2×10^5 × 18 ≈ 1.8×10^8次操作。这个量级在C++里用sort勉强能跑，但洛谷的评测机不一定给你面子，尤其是常数大的时候，TLE是大概率事件。

所以我们需要一个每轮只需要O(n)时间来维护有序性的方案。这个方案的核心洞察是：每轮比赛结束后，胜者组内部仍然有序，败者组内部也仍然有序。为什么？因为比赛前所有人是按分数排好序的，胜者都是每对中分数较高的那位（注意，是赛前分数，不是实力值），所以胜者组的分数在赛前就是非递增的；比赛后每人加1分，这个相对顺序不变。败者组同理，赛前分数非递增，赛后都不加分，相对顺序也不变。于是每轮结束后，我们只需要把两个有序序列合并成一个有序序列，这就是归并排序中"归并"这一步的操作，时间复杂度O(n)。

3. 暴力解法的瓶颈在哪里

3.1 直接排序的思路与代码

先看看最直观的写法。每轮开始前，用sort按分数降序、编号升序排列，然后遍历数组，每两个一组比较实力值，更新分数。代码大概长这样：

#include <bits/stdc++.h> using namespace std; struct Player { int id, score, power; }; bool cmp(const Player &a, const Player &b) { if (a.score != b.score) return a.score > b.score; return a.id < b.id; } int main() { int n, r, q; cin >> n >> r >> q; vector<Player> players(2 * n); for (int i = 0; i < 2 * n; i++) { players[i].id = i + 1; cin >> players[i].score; } for (int i = 0; i < 2 * n; i++) { cin >> players[i].power; } for (int round = 0; round < r; round++) { sort(players.begin(), players.end(), cmp); for (int i = 0; i < 2 * n; i += 2) { if (players[i].power > players[i + 1].power) { players[i].score++; } else { players[i + 1].score++; } } } sort(players.begin(), players.end(), cmp); cout << players[q - 1].id << endl; return 0; }

这段代码逻辑上完全正确，但性能上过不去。问题就出在那个sort上——每轮都做一次全量排序，完全没有利用上一轮的结果。

3.2 复杂度实测与TLE分析

我拿n=100000、r=50的数据跑过这个暴力版本，在本地机器上大概需要3到4秒，而洛谷的时限通常是1秒。差距在哪里？sort的每次比较都涉及结构体读取和分支判断，常数不小。而且每轮排序时，序列其实已经"接近有序"了——胜者组和败者组各自有序，只是交错在一起。sort用的是内省排序（快排+堆排+插排），它不会识别这种"两个有序段交错"的模式，所以还是按O(n log n)来跑。

有人会想，那用stable_sort或者merge行不行？stable_sort底层是归并排序，复杂度还是O(n log n)，没有本质改善。merge倒是O(n)，但你需要先把胜者组和败者组分别提取出来，再合并回去，这个提取和写回的过程也是O(n)，总体是O(n)每轮，这才是正解。

注意：不要试图用sort加自定义比较来"优化"，比较函数的开销本身就很大，而且算法复杂度没变，优化常数救不了数量级。

4. 归并排序思想如何适配这道题

4.1 胜者组与败者组的有序性证明

这是整道题最核心的洞察，我把它单独拎出来讲清楚。假设第k轮比赛前，所有选手按分数降序排列为数组A。比赛配对是(A[0], A[1]), (A[2], A[3]), ...。对于每一对，实力值高的获胜。注意，获胜者的赛前分数不一定比失败者高——比如A[0]分数100，A[1]分数99，但A[1]实力更强，那么A[1]获胜，A[0]失败。所以胜者组的成员来自每一对中实力较强的那位，他们的赛前分数在各自对中是较低或较高的，但胜者组内部的分数顺序是什么样的？

关键点：A本身是按分数降序的，所以A[0] ≥ A[1] ≥ A[2] ≥ A[3] ≥ ...。对于第i对(A[2i], A[2i+1])，胜者的赛前分数是这两个中的一个，所以胜者的赛前分数 ≤ A[2i]（因为A[2i]是这对中较大的）。同时，对于第i+1对，胜者的赛前分数 ≤ A[2i+2]。由于A[2i] ≥ A[2i+2]，我们不能直接得出第i对胜者分数 ≥ 第i+1对胜者分数，因为第i对胜者可能是A[2i+1]，而A[2i+1]可能小于A[2i+2]。

等等，这里需要更仔细地分析。实际上，胜者组的分数序列是否有序，取决于配对方式。让我重新想一下：A[0] ≥ A[1] ≥ A[2] ≥ A[3] ≥ ...。第0对胜者分数是max(A[0], A[1])对应的分数，但分数和实力无关，所以胜者可能是A[0]也可能是A[1]。如果胜者是A[1]，其分数是A[1]的分数；第1对胜者可能是A[2]或A[3]，其分数是A[2]或A[3]的分数。由于A[1] ≥ A[2] ≥ A[3]，所以第0对胜者分数（A[1]）≥ 第1对胜者分数（A[2]或A[3]）。同理可推，胜者组的分数序列是非递增的。

这个证明的关键在于：每一对的胜者分数，至少不小于下一对中任意一人的分数。因为下一对中分数最高的是A[2i+2]，而A[2i+1] ≥ A[2i+2]，所以第i对胜者分数（无论是A[2i]还是A[2i+1]）都 ≥ A[2i+1] ≥ A[2i+2] ≥ 第i+1对胜者分数。证毕。

败者组同理：第i对败者分数 ≥ A[2i+1] ≥ A[2i+2] ≥ 第i+1对败者分数。所以败者组分数也是非递增的。

比赛后，胜者组每人加1分，败者组不变。加1分不改变组内相对顺序，所以胜者组和败者组各自仍然有序。于是每轮结束后，我们有两个有序序列，只需要合并它们。

4.2 每轮O(n)合并的具体操作

合并两个有序序列的标准做法是双指针。设胜者组数组为W，败者组数组为L，两者都按分数降序、编号升序排列。我们用两个指针i和j分别指向W和L的开头，每次比较W[i]和L[j]的排序优先级，把优先级高的放入结果数组，对应指针后移。这个过程和归并排序的merge步骤完全一样。

排序优先级的定义：分数高的优先；分数相同则编号小的优先。写成比较函数就是：

bool higherPriority(const Player &a, const Player &b) { if (a.score != b.score) return a.score > b.score; return a.id < b.id; }

合并时，如果higherPriority(W[i], L[j])为真，就选W[i]，否则选L[j]。注意这里不能用简单的>=，因为分数相同时还要看编号，必须用完整的比较逻辑。

每轮的操作流程：

1. 当前数组已经有序（第一轮需要先排一次序）。
2. 遍历数组，每两个一组比较实力值，胜者放入W，败者放入L。
3. 双指针合并W和L，写回原数组。
4. 重复r轮。

第一轮之前需要一次O(n log n)的排序，之后每轮都是O(n)。总复杂度O(n log n + r × n)，代入数据量大概是2×10^5 × 18 + 50 × 2×10^5 ≈ 3.6×10^6 + 10^7 ≈ 1.36×10^7，比暴力版本的1.8×10^8少了一个数量级，轻松过题。

5. 代码实现中的关键细节与易错点

5.1 结构体设计与比较函数

结构体里存三个字段：编号id、分数score、实力值power。编号从1开始，因为题目输出的是编号。比较函数要严格按题目要求写，分数降序、编号升序。这里有个小技巧：可以把比较逻辑封装成一个函数，在初始排序和每轮合并时复用，避免写重复代码。

struct Player { int id, score, power; }; bool cmp(const Player &a, const Player &b) { if (a.score != b.score) return a.score > b.score; return a.id < b.id; }

初始排序用sort(players.begin(), players.end(), cmp)。注意sort是不稳定的，但因为我们的比较函数已经包含了编号作为二级条件，所以稳定性不影响结果——编号是唯一的，不会出现两个选手完全相等的情况。

5.2 胜者组与败者组的临时存储

每轮需要两个临时数组存胜者和败者。可以用vector<Player>，每轮清空再填充。但频繁的clear和push_back可能带来性能开销，更好的做法是预分配固定大小的数组，用计数器记录实际长度。

vector<Player> win(n), lose(n); int winCnt, loseCnt;

每轮开始时winCnt = loseCnt = 0，然后遍历原数组，胜者写入win[winCnt++]，败者写入lose[loseCnt++]。这样避免了动态内存分配的开销。

5.3 合并时的指针边界处理

合并时两个指针分别遍历win和lose，注意边界条件。当其中一个数组遍历完后，直接把另一个数组剩余部分全部拷贝过去。这里容易犯的错误是忘记处理剩余部分，或者在比较时越界访问。

int i = 0, j = 0, k = 0; while (i < winCnt && j < loseCnt) { if (cmp(win[i], lose[j])) { players[k++] = win[i++]; } else { players[k++] = lose[j++]; } } while (i < winCnt) players[k++] = win[i++]; while (j < loseCnt) players[k++] = lose[j++];

这段代码是归并排序的标准写法，但在这道题里，它的语义是"按优先级合并两个有序序列"，而不是"排序"。理解这一点很重要，因为很多人学归并排序时只记住了代码模板，没理解它在做什么，换一个场景就不会用了。

提示：合并时用cmp(win[i], lose[j])而不是!cmp(lose[j], win[i])，因为cmp是严格弱序，两者在相等时都返回false，需要明确选哪一个。这里选win[i]当cmp为真时，意味着win[i]优先级更高。

5.4 输入输出效率优化

数据量到10^5级别，用cin和cout可能会超时。建议加上ios::sync_with_stdio(false)和cin.tie(0)，或者直接用scanf和printf。这是竞赛中的常规操作，但新手经常忽略。

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

另外，输出只需要输出第q名选手的编号，不需要输出整个排名，所以最后直接取players[q-1].id即可。

6. 完整代码与逐段解析

6.1 完整AC代码

#include <bits/stdc++.h> using namespace std; struct Player { int id, score, power; }; bool cmp(const Player &a, const Player &b) { if (a.score != b.score) return a.score > b.score; return a.id < b.id; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, r, q; cin >> n >> r >> q; int total = 2 * n; vector<Player> players(total); vector<Player> win(n), lose(n); for (int i = 0; i < total; i++) { players[i].id = i + 1; cin >> players[i].score; } for (int i = 0; i < total; i++) { cin >> players[i].power; } sort(players.begin(), players.end(), cmp); for (int round = 0; round < r; round++) { int winCnt = 0, loseCnt = 0; for (int i = 0; i < total; i += 2) { if (players[i].power > players[i + 1].power) { players[i].score++; win[winCnt++] = players[i]; lose[loseCnt++] = players[i + 1]; } else { players[i + 1].score++; win[winCnt++] = players[i + 1]; lose[loseCnt++] = players[i]; } } int i = 0, j = 0, k = 0; while (i < winCnt && j < loseCnt) { if (cmp(win[i], lose[j])) { players[k++] = win[i++]; } else { players[k++] = lose[j++]; } } while (i < winCnt) players[k++] = win[i++]; while (j < loseCnt) players[k++] = lose[j++]; } cout << players[q - 1].id << endl; return 0; }

6.2 关键代码段的逻辑说明

初始排序那一步不能省。第一轮比赛前，选手的顺序是输入顺序，不是按分数排的，所以必须先排一次。这次排序是O(n log n)，只做一次，不影响整体复杂度。

每轮比赛的主循环里，i += 2的步长是因为每两个选手配对。注意比较的是power而不是score，这是题目规则——实力值决定胜负，分数只是排名依据。胜者分数加1，败者不变。然后胜者放入win数组，败者放入lose数组。

合并部分的三个while循环是标准归并写法。第一个while处理两个数组都还有元素的情况，后两个while处理剩余元素。这里用cmp函数来决定取哪个，保证了分数降序、编号升序的排序规则。

最后输出players[q-1].id，因为数组下标从0开始，第q名对应下标q-1。

6.3 复杂度对比表格

这个表格清楚地展示了为什么归并合并是正解。关键区别在于每轮的操作从"全量排序"变成了"合并两个有序序列"，复杂度降了一个数量级。

7. 调试过程中容易踩的坑

7.1 比较函数写反导致答案错误

最常见的错误是把分数降序写成了升序，或者编号升序写成了降序。这种错误不会导致程序崩溃，但答案会完全错误。建议在本地用题目给的样例数据测试，样例通常能覆盖分数相同的情况，如果编号顺序不对，样例就会挂。

另一个隐蔽的错误是在合并时用了错误的比较方向。比如写成了if (cmp(lose[j], win[i]))，这样会把优先级低的先放进去，结果整个数组变成升序，完全反了。这种错误在调试时不容易发现，因为程序逻辑看起来是对的，只是结果不对。建议在合并后打印一下数组，确认排序是否符合预期。

7.2 胜者组败者组数组越界

win和lose数组的大小是n，因为每轮有n场比赛，胜者n人，败者n人。这个大小是固定的，不会越界。但如果你用了vector并且每轮clear再push_back，要注意clear不会释放内存，只是把size设为0，所以性能上没问题。但如果你在clear之前就访问了元素，可能会读到旧数据。

还有一种情况是，如果你把win和lose定义在循环内部，每轮都会重新构造vector，带来不必要的开销。建议定义在循环外部，每轮重置计数器即可。

7.3 分数更新顺序影响结果

比赛时，胜者分数加1，败者不变。这个操作必须在把选手放入win和lose数组之前完成，因为放入数组后，数组里的分数就是更新后的分数，合并时用的是更新后的分数。如果你先放入数组再更新分数，那么win数组里的分数是旧的，合并时排序就错了。

具体来说，正确的顺序是：比较power → 胜者score++ → 胜者放入win，败者放入lose。这个顺序不能乱。

7.4 初始排序遗漏或重复

初始排序只能做一次，在比赛开始前。如果你在每轮循环内部都做一次初始排序，那就退化成了暴力解法，复杂度还是O(r × n log n)。如果你完全不做初始排序，第一轮比赛时选手顺序是输入顺序，配对就错了，结果也会错。

正确的做法是在读入数据后、进入比赛循环前，做一次sort。之后每轮只做合并，不再做全量排序。

8. 从这道题延伸出的通用技巧

8.1 利用"部分有序"降低复杂度

这道题的核心思想是：如果数据在操作后仍然保持某种有序性，就不要重新排序，而是利用这个有序性做线性合并。这个思想在很多问题里都有应用，比如多路归并、外部排序、数据库的归并连接等。

具体到竞赛中，如果你发现每轮操作后，数据可以分成几个各自有序的部分，那么就可以用归并的方式合并，把每轮的O(n log n)降到O(n)。识别这种模式的关键是分析操作对有序性的影响——加一个常数、乘一个正数、或者按固定规则分组，通常都不会破坏组内有序性。

8.2 归并排序的实战价值

很多人学归并排序只是为了应付考试，觉得实际中都用sort。但这道题说明，归并排序的"合并两个有序序列"这个操作本身就是一个强大的工具，它不仅仅用于排序，还可以用于维护有序性。当你需要频繁地"插入一批元素并保持有序"时，归并合并往往比重新排序更高效。

另一个常见的应用场景是"归并两个有序链表"，这在操作系统的任务调度、数据库的索引合并中都有实际应用。理解归并的本质——双指针扫描两个有序序列，按优先级选取——比记住代码模板重要得多。

8.3 竞赛中的常数优化意识

即使算法复杂度对了，常数太大也可能TLE。这道题里，我用vector预分配、避免动态内存分配、用ios::sync_with_stdio(false)加速输入输出，这些都是常规的常数优化手段。在竞赛中，养成这些习惯能帮你多过几道题。

另外，结构体的内存布局也会影响性能。把频繁访问的字段放在前面，或者用数组分离存储（比如id、score、power各用一个数组），有时能提高缓存命中率。不过这道题的数据量下，结构体数组已经够用了，不需要过度优化。

9. 个人实操体会与建议

我第一次做这道题的时候，也是直接sort硬怼，结果TLE了三次。后来看了题解才明白，原来每轮比赛后胜者组和败者组各自有序，只需要合并就行。这个洞察让我意识到，很多算法题的优化点不在于代码怎么写，而在于你对问题结构的理解有多深。

我的建议是，做这类题的时候，先不要急着写代码，而是拿纸笔模拟几轮比赛，观察数据的变化规律。你会发现，胜者组的分数始终比败者组同位置的分数高（或相等），而且组内顺序不变。这个观察一旦建立，优化方案就呼之欲出了。

另外，归并排序的代码一定要自己手写几遍，不要复制粘贴。手写的过程中，你会遇到指针越界、比较方向写反、剩余元素处理遗漏等问题，这些坑踩过了，下次才能避开。我在教别人的时候，经常让他们先写一个"合并两个有序数组"的独立函数，测试通过后再套用到这道题里，这样出错概率会小很多。

最后说一个调试技巧：如果答案不对，先检查比较函数，再检查合并逻辑，最后检查分数更新顺序。这三个地方是错误的高发区。用题目样例测试时，可以手动模拟一遍，看看你的程序输出和手动模拟的结果是否一致。如果不一致，就在关键步骤打印中间结果，逐步定位问题。