信息学奥赛刷题避坑指南：以‘分数线划定’为例，详解stable_sort与自定义cmp的坑

信息学奥赛刷题避坑指南：多关键字排序中的stable_sort与自定义cmp陷阱

在信息学竞赛的赛场上，排序算法就像一把双刃剑——用得好可以轻松斩获高分，用不好则可能让你在看似简单的题目上栽跟头。特别是当遇到需要先按成绩降序，再按编号升序这类多关键字排序问题时，很多选手都会在自定义比较函数和排序稳定性上踩坑。今天我们就以经典的"分数线划定"问题为例，深入剖析这些陷阱背后的原理。

1. 多关键字排序的常见误区

参加过NOIP/NOI系列比赛的选手应该都熟悉这类场景：给定n位考生的编号和成绩，要求先按成绩从高到低排序，成绩相同时按编号从小到大排序。看似简单的需求，在实际编码时却暗藏玄机。

1.1 错误的自定义比较函数写法

很多初学者会尝试这样写比较函数：

bool cmp(Stu a, Stu b) { if(a.s != b.s) return a.s > b.s; return a.k < b.k; }

看起来逻辑清晰，但在某些情况下会产生意想不到的结果。问题出在比较函数的严格弱序要求上。C++标准要求比较函数必须满足以下条件：

• 反自反性：cmp(a,a)必须为false
• 反对称性：如果cmp(a,b)为true，则cmp(b,a)必须为false
• 传递性：如果cmp(a,b)和cmp(b,c)都为true，则cmp(a,c)必须为true

1.2 实际案例分析

假设有以下三个学生数据：

使用上述cmp函数排序后，输出顺序应该是：1003(90)、1001(85)、1002(85)。但如果cmp函数实现有误，可能会导致1002排在1001前面，这与题目要求相悖。

2. stable_sort的妙用场景

当简单的sort无法满足需求时，stable_sort就派上用场了。两者的核心区别在于：

2.1 何时需要稳定排序

在分数线划定问题中，如果我们先按编号排序，再按成绩排序，使用stable_sort可以保证：

1. 第一次排序后，所有学生按编号升序排列
2. 第二次排序时，相同成绩的学生会保持之前的相对顺序（即编号小的仍然在前）

// 先按编号排序 stable_sort(stu+1, stu+1+n, [](Stu a, Stu b){return a.k < b.k;}); // 再按成绩排序 stable_sort(stu+1, stu+1+n, [](Stu a, Stu b){return a.s > b.s;});

2.2 性能考量

虽然stable_sort能保证稳定性，但在大规模数据下可能比sort稍慢：

• 数据量<1000时，差异可以忽略
• 数据量在5000左右时，stable_sort可能慢10-20%
• 极端情况下(1e6数据)，可能慢30-50%

在竞赛中，通常数据规模不会太大，所以使用stable_sort换取正确性是值得的。

3. 自定义比较函数的正确姿势

编写健壮的自定义比较函数需要注意以下几点：

3.1 参数传递方式

优先使用常量引用传递参数，避免不必要的拷贝：

bool cmp(const Stu &a, const Stu &b) { if(a.s != b.s) return a.s > b.s; return a.k < b.k; }

3.2 处理边界情况

良好的比较函数应该处理所有可能的输入组合：

1. 完全相同对象的比较
2. 部分属性相同的比较
3. 所有属性都不同的比较

3.3 Lambda表达式写法

C++11后，可以直接在sort调用处使用lambda表达式：

sort(stu+1, stu+1+n, [](const Stu &a, const Stu &b) { return tie(b.s, a.k) < tie(a.s, b.k); });

这里使用了tie创建临时元组进行比较，代码更简洁但可能影响可读性。

4. 实战技巧与平台差异

不同在线评测平台对排序的实现可能有细微差别，需要注意：

4.1 OpenJudge的特殊情况

在OpenJudge上提交时，以下几点需要特别注意：

• 某些老题可能使用较旧编译器版本
• 内存限制可能比洛谷更严格
• 输出格式要求可能更精确

4.2 洛谷的优化建议

洛谷的现代评测环境支持C++17特性，可以这样优化：

struct Stu { int k, s; auto tied() const { return tuple(-s, k); } }; ... sort(stu+1, stu+1+n, [](const Stu &a, const Stu &b){ return a.tied() < b.tied(); });

4.3 调试技巧

当排序结果不符合预期时，可以：

1. 打印中间排序结果
2. 检查比较函数的所有可能分支
3. 使用小规模测试数据验证
4. 对比stable_sort和sort的结果差异

5. 其他排序方法对比

除了标准库的排序算法，选手也可以考虑其他实现方式：

5.1 冒泡排序实现

虽然时间复杂度较高(O(n²))，但在小数据量(如n≤1000)时足够使用：

for(int i=1; i<=n-1; ++i) for(int j=1; j<=n-i; ++j) if(s[j]<s[j+1] || (s[j]==s[j+1]&&k[j]>k[j+1])) swap(s[j],s[j+1]), swap(k[j],k[j+1]);

5.2 计数排序+插入排序

当成绩范围有限时(如0-100分)，可以采用：

vector<int> score[101]; // 每个分数对应一个编号列表 for(int i=0; i<n; ++i) { int k, s; cin >> k >> s; // 使用lower_bound保持插入有序 auto it = lower_bound(score[s].begin(), score[s].end(), k); score[s].insert(it, k); }

5.3 性能对比表格

6. 常见问题解答

Q：为什么我的排序结果在本地和OJ上不一样？

A：可能原因包括：

• 比较函数不符合严格弱序
• 使用了未定义行为（如越界访问）
• 不同平台STL实现差异

Q：什么时候必须用stable_sort？

A：当且仅当：

1. 需要保持相等元素的原始顺序
2. 采用多趟排序策略时
3. 题目明确要求稳定排序

Q：自定义比较函数导致TLE怎么办？

A：优化建议：

1. 改用引用传递参数
2. 简化比较逻辑
3. 避免在cmp中调用复杂函数

在实际刷题过程中，我发现很多选手会在类似分数线划定这样的基础题目上意外失分。有一次在帮学弟调试代码时，发现他的排序结果总是偶尔出错，最终排查发现是比较函数没有处理好所有边界情况。这也提醒我们，看似简单的排序问题往往隐藏着不少陷阱，需要我们在平时练习中就养成严谨的编码习惯。