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[j1] || (scores[j] scores[j1] ids[j] ids[j1])) { swap(scores[j], scores[j1]); swap(ids[j], ids[j1]); } } } 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²)对于n5000循环次数约为2500万次空间复杂度O(n)优点不依赖STL有助于理解排序原理缺点效率低在大数据量时可能超时4. 计数排序插入排序特定场景的优化当成绩范围有限时如本题中成绩≤100可以采用计数排序插入排序的混合策略。这种方法在成绩分布集中的情况下效率极高。#include iostream #include vector using namespace std; vectorint 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)优点当kn时效率极高缺点成绩范围大时空间消耗大且实现较复杂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. 四种解法对比与选择策略为了帮助大家在实际竞赛中快速选择合适的方法我们总结四种解法的特点解法时间复杂度空间复杂度编码复杂度适用场景结构体sortO(n log n)O(n)低通用场景推荐首选冒泡排序O(n²)O(n)中教学用途实际竞赛不推荐计数插入O(n k)O(n k)高成绩范围小(k小)时高效stable_sortO(n log n)O(n)中需要保持稳定性的场景在实际比赛中建议优先考虑结构体sort的方案它提供了最佳的平衡点代码简洁、效率高、可读性好。只有当题目有特殊要求如明确需要稳定性或数据范围特殊时才考虑其他方案。选择排序算法的几个考量因素数据规模n的大小直接影响算法选择数据特性是否部分有序、键值范围等稳定性要求是否需要保持相同键值的相对顺序空间限制是否有严格的内存限制编码时间竞赛中时间宝贵选择实现快速的方案在NOIP/CSP等竞赛中掌握sort函数的灵活应用可以解决80%以上的排序需求。建议重点练习结构体排序方法并理解比较函数的编写规则。