NOIP2009普及组真题解析：用C++搞定分数线划定，从冒泡到STL sort的四种解法
NOIP2009普及组真题解析：用C++搞定分数线划定，从冒泡到STL sort的四种解法
在信息学奥赛的备赛过程中，排序算法是每个选手必须掌握的核心技能。2009年NOIP普及组的"分数线划定"题目，恰好为我们提供了一个绝佳的练习平台，让我们能够从多个角度理解排序算法的实际应用。这道题目看似简单，却蕴含着丰富的算法思想和工程实践价值。
对于初学者而言，这道题的价值不仅在于完成题目要求，更在于通过不同解法的对比，深入理解算法效率、代码可读性和工程实践之间的平衡。我们将从最基础的冒泡排序开始，逐步过渡到更高级的STL算法，完整呈现一个竞赛选手的思维进化过程。
1. 问题分析与基础解法
1.1 题目要求解析
题目要求我们根据考生的报名号和成绩，确定面试的分数线。具体规则是：计划录取人数的150%（向下取整）名考生的分数即为分数线，所有不低于该分数线的考生都将进入面试。当有同分考生时，按报名号升序排列。
关键数据范围：
- 考生人数n：1 ≤ n ≤ 5000
- 计划录取人数m：1 ≤ m ≤ n
- 报名号k：1000 ≤ k ≤ 9999
- 成绩s：1 ≤ s ≤ 100
1.2 冒泡排序实现
作为最直观的排序方法，冒泡排序虽然效率不高（O(n²)），但对于n≤5000的数据规模完全足够。我们先来看基础实现：
#include <iostream> using namespace std; int main() { int k[5005], s[5005], n, m; 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]); } } int line = s[int(m*1.5)]; int ct = 0; 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; }这种解法的优势在于：
- 代码逻辑直观，易于理解
- 不依赖任何高级语言特性
- 适合算法初学者理解排序过程
但缺点也很明显：
- 排序效率较低
- 代码可读性和维护性较差
- 数据耦合度高（报名号和成绩分开存储）
2. 结构体与自定义排序
2.1 使用结构体组织数据
为了提高代码的可读性和可维护性，我们引入结构体来封装考生信息：
struct Student { int id; // 报名号 int score; // 成绩 };这种封装方式使得相关数据被组织在一起，大大提高了代码的清晰度。同时，我们可以利用C++的sort函数进行高效排序。
2.2 自定义比较函数
STL的sort函数允许我们通过自定义比较函数来实现复杂的排序规则：
bool compare(const Student &a, const Student &b) { if(a.score != b.score) return a.score > b.score; // 成绩降序 return a.id < b.id; // 报名号升序 }完整实现代码如下：
#include <iostream> #include <algorithm> using namespace std; struct Student { int id, score; }; bool compare(const Student &a, const Student &b) { if(a.score != b.score) return a.score > b.score; return a.id < b.id; } int main() { Student stu[5005]; int n, m; cin >> n >> m; for(int i = 0; i < n; ++i) cin >> stu[i].id >> stu[i].score; sort(stu, stu + n, compare); int line = stu[int(m*1.5) - 1].score; int count = 0; for(int i = 0; i < n; ++i) if(stu[i].score >= line) count++; cout << line << ' ' << count << endl; for(int i = 0; i < count; ++i) cout << stu[i].id << ' ' << stu[i].score << endl; return 0; }这种解法的优势：
- 代码结构清晰，可读性强
- 排序效率高（O(nlogn)）
- 数据组织更合理
3. 进阶：STL算法与Lambda表达式
3.1 使用Lambda表达式
C++11引入的Lambda表达式可以让我们的代码更加简洁：
sort(stu, stu + n, [](const Student &a, const Student &b) { return a.score > b.score || (a.score == b.score && a.id < b.id); });3.2 稳定排序的应用
在某些特殊情况下，我们可能需要保持相等元素的原始顺序。这时可以使用stable_sort：
// 先按报名号排序（稳定） stable_sort(stu, stu + n, [](const Student &a, const Student &b) { return a.id < b.id; }); // 再按成绩排序（稳定） stable_sort(stu, stu + n, [](const Student &a, const Student &b) { return a.score > b.score; });虽然对于本题来说，普通的sort已经足够，但了解stable_sort的特性对于解决更复杂的问题很有帮助。
4. 性能分析与优化
4.1 不同解法的性能对比
| 解法类型 | 时间复杂度 | 空间复杂度 | 代码复杂度 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | 低 | 教学、小规模数据 |
| STL sort | O(nlogn) | O(n) | 中 | 通用场景 |
| 稳定排序 | O(nlogn) | O(n) | 中 | 需要保持原始顺序 |
| 计数排序 | O(n+k) | O(k) | 高 | 数据范围小的情况 |
4.2 计数排序的特殊解法
当成绩范围有限（如本题1-100分）时，可以使用计数排序实现O(n)时间复杂度的解法：
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> scores[101]; // 每个分数对应一个报名号列表 int n, m; cin >> n >> m; for(int i = 0; i < n; ++i) { int id, score; cin >> id >> score; scores[score].push_back(id); } // 对每个分数的报名号列表排序 for(int i = 1; i <= 100; ++i) sort(scores[i].begin(), scores[i].end()); int total = 0, line = 0; for(int i = 100; i >= 1; --i) { total += scores[i].size(); if(total >= int(m * 1.5)) { line = i; break; } } // 重新计算实际人数（可能有更多人同分） total = 0; for(int i = 100; i >= line; --i) total += scores[i].size(); cout << line << ' ' << total << endl; for(int i = 100; i >= line; --i) for(int id : scores[i]) cout << id << ' ' << i << endl; return 0; }这种解法在特定条件下（成绩范围小）性能最优，但代码复杂度较高，通用性不如基于比较的排序。
5. 工程实践建议
5.1 代码风格与可读性
在竞赛编程中，良好的代码风格同样重要：
- 使用有意义的变量名（如studentCount而非n）
- 适当添加注释说明关键步骤
- 保持一致的缩进和代码布局
5.2 调试技巧
排序类题目常见的调试问题：
- 边界条件处理（如第m*1.5名正好有多个同分考生）
- 比较函数的正确性（确保满足严格弱序）
- 数组下标越界（特别是从0开始还是从1开始）
5.3 测试用例设计
针对本题，应该准备以下类型的测试用例：
- 常规情况（有明确分数线）
- 同分考生较多的情况
- 边界情况（n和m的最小/最大值）
- 所有考生同分的情况
例如：
// 测试用例1：常规情况 5 3 1001 90 1002 85 1003 95 1004 90 1005 80 // 测试用例2：多人同分 6 4 2001 80 2002 80 2003 85 2004 75 2005 85 2006 90在实际比赛中，建议先手动计算预期结果，再与程序输出对比。