用C++解NOIP真题：P1068分数线划定，从冒泡到STL sort的四种解法对比
用C++解NOIP真题：P1068分数线划定，从冒泡到STL sort的四种解法对比
在信息学奥赛（NOIP/CSP）的备战过程中，排序算法是每位选手必须掌握的核心技能。2009年NOIP普及组的《分数线划定》一题，看似简单却暗藏玄机——它要求选手在处理多重排序规则时，能够灵活选择最优解法。这道题的数据规模虽然不大（最多5000条记录），但恰恰为我们提供了绝佳的教学案例：从最基础的冒泡排序开始，逐步升级到STL的高阶用法，甚至探索混合算法的可能性。
对于初学者而言，这道题的价值不仅在于"AC"（通过测试），更在于理解不同解法的适用场景与性能差异。本文将带您深入剖析四种典型解法：传统冒泡排序、结构体结合STL sort、两趟稳定排序（stable_sort）以及计数排序与插入排序的混合应用。每种方法都有其独特的实现逻辑和优化思路，我们将从代码复杂度、执行效率、内存占用等多个维度进行对比，帮助您在竞赛中做出更明智的选择。
1. 基础解法：冒泡排序的双重条件实现
让我们从最朴素的冒泡排序开始。虽然在实际竞赛中很少会真正使用这种O(n²)的算法，但理解它的实现原理对夯实基础至关重要。在分数线划定问题中，我们需要先按成绩降序排列，成绩相同时再按报名号升序排列——这种双重条件的排序规则，正是考察的重点。
#include <bits/stdc++.h> using namespace std; #define N 5005 int main() { int k[N], s[N], n, m, line, ct = 0; cin >> n >> m; for(int i = 1; i <= n; ++i) cin >> k[i] >> s[i]; // 冒泡排序核心逻辑 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]); } } line = s[int(m*1.5)]; for(int i = 1; i <= n; ++i) if(s[i] >= line) ct++; cout << line << ' ' << ct << endl; for(int i = 1; i <= ct; ++i) cout << k[i] << ' ' << s[i] << endl; return 0; }关键点解析：
- 双重条件判断：
s[j] < s[j+1] || (s[j] == s[j+1] && k[j] > k[j+1])这一行代码完美体现了题目要求的排序规则 - 交换逻辑：当条件满足时，需要同时交换成绩和报名号两个数组的值
- 时间复杂度：最坏情况下需要进行约5000×5000=25,000,000次比较和交换
提示：虽然冒泡排序在本题数据规模下仍能通过，但在实际竞赛中应尽量避免使用，除非题目明确限制算法选择。
2. 结构体与STL sort的优雅解法
当数据需要关联多个属性时，结构体是C++中最自然的表达方式。结合STL的sort算法，我们可以写出更简洁、更易维护的代码。这种解法的核心在于自定义比较函数，它决定了排序的规则。
#include <bits/stdc++.h> using namespace std; #define N 5005 struct Stu { int k, s; // k:报名号 s:成绩 }; bool cmp(Stu &a, Stu &b) { if(a.s == b.s) // 分数相同时 return a.k < b.k; // 报名号小的在前 else // 分数不同时 return a.s > b.s; // 成绩高的在前 } int main() { Stu stu[N]; int n, m, line, ct = 0; cin >> n >> m; for(int i = 1; i <= n; ++i) cin >> stu[i].k >> stu[i].s; sort(stu+1, stu+1+n, cmp); // 使用自定义比较函数排序 line = stu[int(m*1.5)].s; for(int i = 1; i <= n; ++i) if(stu[i].s >= line) ct++; cout << line << ' ' << ct << endl; for(int i = 1; i <= ct; ++i) cout << stu[i].k << ' ' << stu[i].s << endl; return 0; }性能对比：
| 指标 | 冒泡排序 | STL sort |
|---|---|---|
| 时间复杂度 | O(n²) | O(nlogn) |
| 代码复杂度 | 中等 | 简单 |
| 内存占用 | 较低 | 中等 |
| 可维护性 | 较差 | 优秀 |
| 适用数据规模 | <1万 | 无限制 |
这种解法的优势不仅在于性能提升，更在于代码的可读性和扩展性。如果需要添加新的排序条件，只需修改cmp函数即可，主逻辑完全不受影响。
3. 稳定排序的应用：两趟排序策略
在某些特殊场景下，我们需要保持相同关键字的原始顺序，这时stable_sort就派上用场了。虽然本题并不严格要求稳定性，但了解这种解法有助于拓宽思路。
#include <bits/stdc++.h> using namespace std; #define N 5005 struct Stu { int k, s; }; bool cmp_k(const Stu &a, const Stu &b) { return a.k < b.k; // 报名号升序 } bool cmp_s(const Stu &a, const Stu &b) { return a.s > b.s; // 成绩降序 } int main() { Stu stu[N]; int n, m, line, ct = 0; cin >> n >> m; for(int i = 1; i <= n; ++i) cin >> stu[i].k >> stu[i].s; // 先按次要条件排序，再按主要条件稳定排序 stable_sort(stu+1, stu+1+n, cmp_k); stable_sort(stu+1, stu+1+n, cmp_s); line = stu[int(m*1.5)].s; for(int i = 1; i <= n; ++i) if(stu[i].s >= line) ct++; cout << line << ' ' << ct << endl; for(int i = 1; i <= ct; ++i) cout << stu[i].k << ' ' << stu[i].s << endl; return 0; }稳定排序的特点：
- 保持相等元素的相对顺序
- 时间复杂度同样是O(nlogn)，但常数因子通常比sort大
- 适用于需要多次排序且要保持前次排序结果的场景
- 在本题中，先按报名号排序，再按成绩稳定排序，等价于单次多条件排序
注意：虽然两趟排序能得到正确结果，但在竞赛中应优先考虑单次多条件排序，除非题目明确要求保持稳定性。
4. 混合算法：计数排序+插入排序的巧妙组合
当数据范围有限时（如本题成绩不超过100分），计数排序可以发挥O(n)的时间复杂度优势。结合插入排序处理同分学生的报名号排序，这种混合算法在特定条件下性能最优。
#include <bits/stdc++.h> using namespace std; int score[105][5005] = {}; // score[i][0]存储长度 int main() { int k, s, n, m, line, ct = 0; cin >> n >> m; // 计数排序+插入排序 for(int i = 1; i <= n; ++i) { cin >> k >> s; // 将k插入score[s]数组，并保持升序 int& len = score[s][0]; score[s][++len] = k; for(int j = len; j > 1; --j) { if(score[s][j] < score[s][j-1]) swap(score[s][j], score[s][j-1]); else break; } } // 确定分数线 int lnum = int(m*1.5); for(int i = 100; i >= 0; --i) { ct += score[i][0]; if(ct >= lnum) { line = i; break; } } cout << line << ' ' << ct << endl; // 输出结果 for(int i = 100; i >= line; --i) for(int j = 1; j <= score[i][0]; ++j) cout << score[i][j] << ' ' << i << endl; return 0; }算法分析：
- 计数排序部分：O(n)时间复杂度处理成绩分布
- 插入排序部分：最坏情况下O(k²)，k为同分人数，但本题中k≤5000
- 空间复杂度：O(max_score×n)，当成绩范围很大时不适用
- 优势：当成绩范围小而n很大时，效率远超常规排序算法
适用场景判断：
| 情况描述 | 推荐算法 |
|---|---|
| 成绩范围小(如0-100)，n很大 | 计数+插入排序 |
| 成绩范围大，n中等(≤10⁵) | STL sort单次排序 |
| 需要保持相同成绩的原始顺序 | stable_sort两趟 |
| 算法限制(如禁用STL) | 冒泡或其他基础排序 |
5. 竞赛中的实战选择策略
在真实的NOIP/CSP竞赛环境中，选择哪种解法不仅取决于算法效率，还需要考虑以下因素：
代码实现速度：
- 结构体+sort写法通常最快实现
- 冒泡排序虽然效率低，但在时间紧迫时可能更快写出
- 混合算法实现复杂，容易出错，适合有充分时间检查时使用
调试难度：
- 结构体解法：变量组织清晰，调试最容易
- 两趟排序：需要注意排序顺序是否正确
- 混合算法：多维数组操作容易出界，需要仔细检查
- 冒泡排序：虽然简单，但边界条件容易出错
鲁棒性考量：
- STL sort经过充分优化，几乎不会出现性能问题
- 自己实现的排序需要注意特殊测试用例：
- 所有成绩相同
- 所有报名号相同
- 极端数据(如n=1或n=5000)
// 竞赛推荐写法示例 #include <bits/stdc++.h> using namespace std; struct Candidate { int id, score; bool operator<(const Candidate& rhs) const { return score != rhs.score ? score > rhs.score : id < rhs.id; } }; int main() { int n, m; cin >> n >> m; vector<Candidate> candidates(n); for(auto& c : candidates) cin >> c.id >> c.score; sort(candidates.begin(), candidates.end()); int cutoff = candidates[(int)(m*1.5)-1].score; int count = count_if(candidates.begin(), candidates.end(), [cutoff](const Candidate& c) { return c.score >= cutoff; }); cout << cutoff << ' ' << count << '\n'; for(int i = 0; i < count; ++i) cout << candidates[i].id << ' ' << candidates[i].score << '\n'; }优化技巧：
- 使用vector替代原生数组更安全
- 重载operator<比单独写cmp函数更简洁
- 使用count_if算法统计人数更符合现代C++风格
- 统一使用标准输入输出流（关闭同步后可提速）
在实际比赛中，我通常会准备一个排序算法的模板代码，遇到需要排序的题目时，只需根据具体需求调整比较逻辑即可。这种标准化的工作流程可以大幅减少实现时间，把更多精力留给真正的算法难题。