NOIP2009普及组真题解析：用C++的sort函数搞定‘分数线划定’，附四种解法对比-开发者社区

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

在信息学奥赛的备战过程中，排序算法是每位选手必须掌握的核心技能。2009年NOIP普及组的"分数线划定"题目，不仅考察了基础的排序能力，更考验选手对不同排序算法特性的理解。这道题的数据规模虽然不大（最多5000条记录），但恰恰适合用来深入探讨各种排序方法的优劣。

本文将带你从零开始拆解这道经典题目，重点分析C++标准库中sort函数的灵活应用，同时对比结构体排序、冒泡排序、计数排序+插入排序、stable_sort稳定排序四种实现方案。不同于简单的AC题解，我们会深入探讨每种算法的时间复杂度、适用场景和编码技巧，帮助你在竞赛中根据数据特征快速选择最优解法。

1. 题目分析与解题思路

"分数线划定"的题目要求可以简化为：给定n个考生的报名号和成绩，按照成绩从高到低排序，成绩相同时按报名号从小到大排序。然后确定录取分数线为排名第m*1.5（向下取整）的考生成绩，最后输出所有不低于该分数线的考生信息。

关键解题步骤：

数据输入：存储每个考生的报名号和成绩
自定义排序：
- 主排序键：成绩降序
- 次排序键：报名号升序
分数线计算：取第⌊m*1.5⌋个考生的成绩
结果输出：统计并输出所有不低于分数线的考生

注意：题目中的m1.5需要向下取整，C++中可以直接使用int(m1.5)实现。

这道题的数据规模n≤5000，意味着O(n²)的算法（如冒泡排序）也能在规定时间内完成。但在实际竞赛中，养成使用高效算法的习惯非常重要，因为题目数据范围可能会在后续年份调整。

2. 结构体排序：最清晰的解法

使用结构体存储考生信息，配合自定义比较函数，是最直观的解决方案。这种方法代码可读性强，易于维护，是竞赛中的首选方案。

#include <bits/stdc++.h> using namespace std; #define N 5005 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[N]; 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 cutoff = stu[int(m * 1.5)].score; int count = 0; while(count < n && stu[count].score >= cutoff) count++; cout << cutoff << " " << count << endl; for(int i = 0; i < count; ++i) cout << stu[i].id << " " << stu[i].score << endl; return 0; }

性能分析：

时间复杂度：O(n log n)，来自sort函数
空间复杂度：O(n)，存储所有考生信息
优点：代码简洁，逻辑清晰，适合各种规模的数据
缺点：需要额外定义结构体和比较函数

3. 冒泡排序：理解排序本质

虽然在实际竞赛中不推荐使用冒泡排序，但通过实现它可以帮助我们深入理解排序算法的基本原理。下面是使用冒泡排序的解法：

#include <iostream> using namespace std; #define N 5005 int main() { int ids[N], scores[N]; int n, m; cin >> n >> m; for(int i = 0; i < n; ++i) cin >> ids[i] >> scores[i]; // 冒泡排序实现 for(int i = 0; i < n-1; ++i) { for(int j = 0; j < n-i-1; ++j) { if(scores[j] < scores[j+1] || (scores[j] == scores[j+1] && ids[j] > ids[j+1])) { swap(scores[j], scores[j+1]); swap(ids[j], ids[j+1]); } } } int cutoff = scores[int(m * 1.5)]; int count = 0; while(count < n && scores[count] >= cutoff) count++; cout << cutoff << " " << count << endl; for(int i = 0; i < count; ++i) cout << ids[i] << " " << scores[i] << endl; return 0; }

性能分析：

时间复杂度：O(n²)，对于n=5000，循环次数约为2500万次
空间复杂度：O(n)
优点：不依赖STL，有助于理解排序原理
缺点：效率低，在大数据量时可能超时

4. 计数排序+插入排序：特定场景的优化

当成绩范围有限时（如本题中成绩≤100），可以采用计数排序+插入排序的混合策略。这种方法在成绩分布集中的情况下效率极高。

#include <iostream> #include <vector> using namespace std; vector<int> scoreBuckets[101]; // 0-100分 int main() { int n, m; cin >> n >> m; for(int i = 0; i < n; ++i) { int id, score; cin >> id >> score; // 使用插入排序保持每个桶内id有序 auto &bucket = scoreBuckets[score]; auto it = bucket.begin(); while(it != bucket.end() && *it < id) ++it; bucket.insert(it, id); } int cutoff = 0, count = 0; for(int s = 100; s >= 0; --s) { count += scoreBuckets[s].size(); if(count >= int(m * 1.5)) { cutoff = s; break; } } // 重新计算精确的count count = 0; for(int s = 100; s >= cutoff; --s) count += scoreBuckets[s].size(); cout << cutoff << " " << count << endl; for(int s = 100; s >= cutoff; --s) for(int id : scoreBuckets[s]) cout << id << " " << s << endl; return 0; }

性能分析：

时间复杂度：O(n + k)，其中k是成绩范围（101）
空间复杂度：O(n + k)
优点：当k<<n时，效率极高
缺点：成绩范围大时空间消耗大，且实现较复杂

5. stable_sort两阶段排序：保持稳定性的方案

如果需要保持排序稳定性（即相同键值的元素保持原有顺序），可以使用stable_sort进行两阶段排序：

#include <bits/stdc++.h> using namespace std; #define N 5005 struct Student { int id, score; }; bool compareId(const Student &a, const Student &b) { return a.id < b.id; } bool compareScore(const Student &a, const Student &b) { return a.score > b.score; } int main() { Student stu[N]; int n, m; cin >> n >> m; for(int i = 0; i < n; ++i) cin >> stu[i].id >> stu[i].score; // 先按id排序，保证相同score时id小的在前 stable_sort(stu, stu + n, compareId); // 再按score排序，保持相同score元素的相对顺序 stable_sort(stu, stu + n, compareScore); int cutoff = stu[int(m * 1.5)].score; int count = 0; while(count < n && stu[count].score >= cutoff) count++; cout << cutoff << " " << count << endl; for(int i = 0; i < count; ++i) cout << stu[i].id << " " << stu[i].score << endl; return 0; }

性能分析：

时间复杂度：O(n log n)，但常数因子比普通sort大
空间复杂度：O(n)
优点：保持排序稳定性，适合需要保持相对顺序的场景
缺点：需要两次排序，效率略低

6. 四种解法对比与选择策略

为了帮助大家在实际竞赛中快速选择合适的方法，我们总结四种解法的特点：

解法	时间复杂度	空间复杂度	编码复杂度	适用场景
结构体+sort	O(n log n)	O(n)	低	通用场景，推荐首选
冒泡排序	O(n²)	O(n)	中	教学用途，实际竞赛不推荐
计数+插入	O(n + k)	O(n + k)	高	成绩范围小(k小)时高效
stable_sort	O(n log n)	O(n)	中	需要保持稳定性的场景