NOIP2009普及组真题解析：用C++三种排序方法搞定‘分数线划定’（附完整代码）-平芜编程栈

NOIP2009普及组真题解析：用C++三种排序方法搞定‘分数线划定’（附完整代码）

在信息学奥赛（NOIP/CSP）的备考过程中，排序算法是最基础也是最重要的知识点之一。2009年NOIP普及组的"分数线划定"题目，不仅考察了选手对排序算法的理解和应用能力，更提供了一个绝佳的机会来比较不同排序方法在实际问题中的表现。本文将通过这道经典题目，深入解析C++中三种不同的排序实现方案：标准库sort、手写冒泡排序以及计数排序+插入排序的组合应用。

1. 题目分析与解题思路

"分数线划定"题目要求根据考生的成绩和报名号，确定面试的分数线和进入面试的考生名单。具体规则是：面试人数为计划录取人数的150%（向下取整），然后所有成绩不低于该分数线的考生都将进入面试。如果有多人成绩相同，则按报名号升序排列。

这道题的核心在于多重条件排序：首先按成绩降序排列，成绩相同则按报名号升序排列。对于最多5000个考生的数据规模，虽然O(n²)的排序算法也能胜任，但不同实现方式在代码复杂度、可读性和潜在性能上都有显著差异。

提示：在实际竞赛中，理解题目要求并选择合适的算法往往比直接编码更重要。建议先花1-2分钟仔细分析题目条件和数据范围。

2. 标准库sort解法：简洁高效的首选

C++标准库中的sort函数基于快速排序实现，平均时间复杂度为O(n log n)，是解决这类排序问题的首选方案。下面是使用sort的完整实现：

#include <bits/stdc++.h> using namespace std; #define N 5005 struct Student { int id, score; }; bool compare(const Student &a, const Student &b) { return a.score != b.score ? a.score > b.score : a.id < b.id; } int main() { Student students[N]; int n, m; cin >> n >> m; for(int i = 0; i < n; ++i) cin >> students[i].id >> students[i].score; sort(students, students + n, compare); int cutoff = students[(int)(m * 1.5) - 1].score; int count = 0; while(count < n && students[count].score >= cutoff) count++; cout << cutoff << " " << count << endl; for(int i = 0; i < count; ++i) cout << students[i].id << " " << students[i].score << endl; return 0; }

这种实现方式的优势在于：

代码简洁：利用结构体和比较函数，清晰地表达了排序规则
性能优越：标准库sort经过高度优化，处理5000个元素几乎瞬间完成
可读性强：逻辑清晰，易于理解和维护

3. 手写冒泡排序：理解算法本质

虽然在实际比赛中很少需要手写排序算法，但通过实现冒泡排序可以深入理解排序的基本原理。下面是冒泡排序的实现：

#include <bits/stdc++.h> using namespace std; #define N 5005 int main() { int ids[N], scores[N], 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 - 1 - i; ++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) - 1]; 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万次
稳定性：通过适当实现可以保证稳定性（相等元素相对顺序不变）
教学价值：帮助理解基本排序原理和交换操作

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

当成绩范围有限（如0-100分）时，可以采用计数排序+插入排序的组合方案：

#include <bits/stdc++.h> using namespace std; vector<int> students[101]; // 按分数分组存储报名号 int main() { int n, m, id, score; cin >> n >> m; for(int i = 0; i < n; ++i) { cin >> id >> score; // 使用插入排序保持每个分数段内报名号有序 auto &group = students[score]; auto it = lower_bound(group.begin(), group.end(), id); group.insert(it, id); } int total = 0, cutoff = 0; for(int s = 100; s >= 0; --s) { total += students[s].size(); if(total >= m * 1.5) { cutoff = s; break; } } // 重新计算实际人数（可能有更多人达到cutoff分数） total = 0; for(int s = 100; s >= cutoff; --s) total += students[s].size(); cout << cutoff << " " << total << endl; for(int s = 100; s >= cutoff; --s) for(int id : students[s]) cout << id << " " << s << endl; return 0; }

这种方法的优势在于：

线性时间复杂度：计数排序部分为O(n)，插入排序部分最坏O(n²)但实际表现良好
空间换时间：需要额外的存储空间来分组存储数据
适合特定场景：当分数范围有限且远小于n时效率最高

5. 三种方法的对比与选择

下表总结了三种实现方式的关键特点：

特性	标准库sort	冒泡排序	计数+插入排序
时间复杂度	O(n log n)	O(n²)	O(n + k)
空间复杂度	O(n)	O(n)	O(n + k)
代码复杂度	低	中	高
适用数据规模	大	小	特定
是否需要额外空间	否	否	是
稳定性	通常不稳定	可稳定	稳定