NOIP2009普及组真题解析：用C++的sort函数搞定‘分数线划定’（附四种解法对比）

NOIP2009普及组真题解析：用C++的sort函数搞定‘分数线划定’（附四种解法对比）

在信息学竞赛的备考过程中，排序算法是最基础也是最重要的知识点之一。2009年NOIP普及组的"分数线划定"题目，正是考察选手对排序算法的理解和应用能力。这道题目看似简单，但其中蕴含的算法选择和优化思路，却值得我们深入探讨。

本文将围绕四种不同的解法展开分析，从结构体sort、冒泡排序到计数排序和stable_sort两趟排序，每种方法都有其独特的适用场景和优劣势。对于正在备战NOIP/CSP等竞赛的初中生或入门级选手来说，理解这些解法的差异并掌握在不同场景下的最佳选择策略，将大大提升解题效率和代码质量。

1. 题目分析与基础思路

"分数线划定"题目要求我们根据考生的报名号和成绩，按照特定规则进行排序后确定录取分数线。具体来说，需要先按成绩降序排序，成绩相同则按报名号升序排序，然后取第⌊m*1.5⌋个人的成绩作为分数线，最后输出所有不低于该分数线的考生信息。

题目给出的数据规模最大为5000，这意味着O(n²)时间复杂度的算法在理论上是可行的。但实际竞赛中，我们还需要考虑代码实现的简洁性、运行效率以及特殊比赛环境下的限制（如早期NOIP对STL的限制）。

核心解题步骤：

1. 输入考生信息（报名号和成绩）
2. 按指定规则排序
3. 确定分数线
4. 统计并输出合格考生信息

2. 四种解法深度对比

2.1 结构体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; }

优势分析：

• 时间复杂度：O(n log n)，效率高
• 代码简洁，逻辑清晰
• 充分利用STL，减少手写代码量

适用场景：

• 现代NOIP/CSP竞赛（允许使用STL）
• 需要快速实现且对性能有要求的场景

2.2 冒泡排序解法

这是一种传统的排序方法，不使用结构体，直接在数组上进行操作。

#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; }

性能对比：

适用场景：

• 早期NOIP比赛（限制STL使用）
• 教学演示排序算法原理
• 数据规模非常小的情况

2.3 计数排序+插入排序解法

这种方法利用了成绩范围有限（0-100分）的特点，先按成绩分组，再对每组内的报名号进行排序。

#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; score[s][++score[s][0]] = k; for(int j = score[s][0]; 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)
• 避免了通用排序算法的复杂度
• 内存访问局部性好，实际运行效率可能很高

适用场景：

• 成绩范围明确且有限
• 对特定数据分布有优化需求
• 需要展示非比较排序算法的应用

2.4 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; }

技术要点：

• 第一趟按报名号升序排序（次要关键字）
• 第二趟按成绩降序排序（主要关键字）
• 稳定排序保证相同成绩的考生保持报名号顺序

适用场景：

• 需要展示稳定排序特性的应用
• 多关键字排序的教学示例
• 对排序稳定性有要求的特殊场景

3. 竞赛实战中的选择策略

在实际竞赛环境中，选择哪种解法需要考虑多个因素：

1. 比赛规则限制

• 现代NOIP/CSP：优先使用STL sort
• 早期NOIP限制STL：冒泡排序或手写快排
• 在线评测系统（如洛谷）：选择最简洁高效的实现

2. 数据规模考量

• n ≤ 5000：所有方法都可行
• n ≤ 1000：冒泡排序也可接受
• 成绩范围很小：计数排序优势明显

3. 编码效率与调试

• 结构体sort：编码最快，调试最容易
• 冒泡排序：需要小心边界条件
• 计数排序：需要处理二维数组

4. 性能优化空间

• 对于大规模数据，sort是最佳选择
• 如果题目扩展为动态维护分数线，可能需要更复杂的数据结构

4. 常见错误与优化技巧

在实现这四种解法时，选手常会遇到一些典型问题：

常见错误：

1. 数组下标处理不当（特别是1-based和0-based混用）
2. 多关键字排序时比较函数写错
3. 分数线位置计算错误（注意整数除法）
4. 输出时未正确处理同分考生

优化技巧：

1. 使用ios::sync_with_stdio(false)加速输入输出
2. 对于固定范围数据，优先考虑非比较排序
3. 合理使用结构体使代码更清晰
4. 预先计算避免重复操作

// 输入输出优化示例 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

调试建议：

1. 先用小规模数据测试基本功能
2. 检查边界情况（如所有考生同分）
3. 验证排序结果的稳定性
4. 对比不同解法的输出是否一致

在实际竞赛中，建议优先掌握结构体结合sort的解法，这是最通用且高效的方法。同时理解其他解法的思想，以便在特殊情况下能够灵活应变。对于初学者来说，手写冒泡排序也有助于深入理解排序算法的原理。