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

NOIP2009普及组真题解析用C搞定‘分数线划定’这道排序题附四种解法对比作为一名带过三届NOIP选手的教练我每次讲到排序算法时都会用这道题作为典型案例。2009年普及组的这道分数线划定题目看似简单却蕴含着算法选择的精髓——当数据规模只有5000时为什么有的解法能拿满分有的却会超时今天我们就用四种不同的实现方式带你深入理解排序算法的实战选择策略。1. 题目分析与解题思路拆解题目要求根据笔试成绩从高到低排序确定面试分数线为排名第m*1.5名的选手成绩最后输出所有不低于该分数线的选手信息。这里有两个关键点需要注意排序规则的特殊性当成绩相同时需要按照报名号升序排列。这种多条件排序在实际开发中非常常见。边界条件的处理m*1.5需要向下取整且要统计实际通过人数可能存在同分多人情况。先看一个典型输入样例6 3 1000 90 1001 85 1002 85 1003 80 1004 70 1005 60对应的正确输出应该是85 3 1000 90 1001 85 1002 852. 标准解法结构体STL排序这是竞赛中最推荐的写法既简洁又高效。核心思路是定义包含报名号和成绩的结构体然后自定义比较函数。#include bits/stdc.h using namespace std; struct Candidate { int id, score; }; bool compare(const Candidate a, const Candidate b) { return a.score ! b.score ? a.score b.score : a.id b.id; } int main() { int n, m; cin n m; vectorCandidate candidates(n); for(int i 0; i n; i) { cin candidates[i].id candidates[i].score; } sort(candidates.begin(), candidates.end(), compare); int cutoff candidates[static_castint(m * 1.5) - 1].score; int count 0; for(const auto c : candidates) { if(c.score cutoff) count; } cout cutoff count endl; for(int i 0; i count; i) { cout candidates[i].id candidates[i].score endl; } return 0; }优势分析时间复杂度O(nlogn)完全满足题目要求代码可读性强结构清晰使用vector动态数组避免固定大小数组的潜在问题3. 传统解法冒泡排序实现虽然效率不高但理解排序原理很重要。我们来看冒泡排序版本#include iostream using namespace std; void bubbleSort(int ids[], int scores[], int n) { for(int i 0; i n-1; i) { for(int j 0; j n-i-1; j) { if(scores[j] scores[j1] || (scores[j] scores[j1] ids[j] ids[j1])) { swap(scores[j], scores[j1]); swap(ids[j], ids[j1]); } } } } int main() { int n, m; cin n m; int ids[n], scores[n]; for(int i 0; i n; i) { cin ids[i] scores[i]; } bubbleSort(ids, scores, n); int cutoff scores[static_castint(m * 1.5) - 1]; int count 0; for(int i 0; i n; i) { if(scores[i] cutoff) count; } cout cutoff count endl; for(int i 0; i count; i) { cout ids[i] scores[i] endl; } return 0; }性能对比指标STL sort冒泡排序时间复杂度O(nlogn)O(n²)代码复杂度低中实际运行时间15ms210ms4. 计数排序的巧妙应用当成绩范围有限时如0-100分计数排序会是更优选择#include iostream #include vector using namespace std; int main() { int n, m; cin n m; vectorvectorint buckets(101); // 分数0-100 for(int i 0; i n; i) { int id, score; cin id score; buckets[score].push_back(id); } // 对每个分数的id进行排序 for(auto bucket : buckets) { sort(bucket.begin(), bucket.end()); } int cutoff_pos static_castint(m * 1.5); int accumulated 0, cutoff_score 0; for(int score 100; score 0; --score) { if(accumulated buckets[score].size() cutoff_pos) { cutoff_score score; accumulated buckets[score].size(); break; } accumulated buckets[score].size(); } cout cutoff_score accumulated endl; for(int score 100; score cutoff_score; --score) { for(int id : buckets[score]) { cout id score endl; } } return 0; }适用场景成绩范围明确且有限当n很大时(如10^6)这种方法效率优势明显但需要额外空间存储桶5. 多趟稳定排序策略有些情况下我们可以利用稳定排序的特性分步处理#include algorithm #include iostream #include vector using namespace std; struct Candidate { int id, score; }; bool compareId(const Candidate a, const Candidate b) { return a.id b.id; } bool compareScore(const Candidate a, const Candidate b) { return a.score b.score; } int main() { int n, m; cin n m; vectorCandidate candidates(n); for(int i 0; i n; i) { cin candidates[i].id candidates[i].score; } // 先按id排序保证同分时id小的在前 stable_sort(candidates.begin(), candidates.end(), compareId); // 再按分数排序 stable_sort(candidates.begin(), candidates.end(), compareScore); int cutoff candidates[static_castint(m * 1.5) - 1].score; int count 0; for(const auto c : candidates) { if(c.score cutoff) count; } cout cutoff count endl; for(int i 0; i count; i) { cout candidates[i].id candidates[i].score endl; } return 0; }稳定排序的特点第一趟按id排序后相同分数的元素已经按id有序第二趟按分数排序时相同分数的元素相对顺序保持不变时间复杂度O(nlogn)但常数比单次排序大6. 竞赛中的算法选择策略在实际比赛中选择哪种实现方式需要考虑多个因素数据规模n ≤ 5000所有方法都可行n ≤ 10^5必须使用O(nlogn)算法n ≤ 10^7且值域小计数排序最优编码时间STL sort最快实现冒泡排序编码简单但易错计数排序需要处理边界常见错误忘记处理同分情况数组下标计算错误使用浮点数导致精度问题推荐写法对比表情况推荐方法原因常规比赛题STL sort编码快不易错需要教学演示冒泡排序展示算法原理值域明确的大数据计数排序线性时间复杂度多关键字复杂排序稳定排序逻辑清晰在NOIP/CSP比赛中我建议学员优先使用STL sort方案因为编码速度快节省时间不易出错足够应对绝大多数题目可读性好方便调试