信息学奥赛刷题笔记用C结构体STL sort搞定OpenJudge NOI 1.10 01排名查询在信息学奥赛的备战过程中掌握高效的数据处理技巧至关重要。今天我们要探讨的是一道经典题目——OpenJudge NOI 1.10 01谁考了第k名这道题看似简单却蕴含着C编程中几个核心概念结构体定义、自定义排序规则以及STL算法的巧妙应用。对于初学者来说这道题提供了一个绝佳的机会让我们能够从读题-建模-实现-调试的完整解题流程中深入理解如何将实际问题转化为代码解决方案。更重要的是通过对比手写排序算法与STL sort的实现方式我们可以直观感受到标准库工具带来的代码简洁性和效率提升。1. 题目分析与数据结构建模1.1 理解题目需求题目要求我们处理一组学生数据每个学生有学号和分数两个属性需要根据分数从高到低排序后输出第k名学生的信息。看似简单的需求背后我们需要考虑几个关键点数据规模虽然示例数据量不大但竞赛中需要考虑效率排序规则降序排列分数高的在前输出格式学号和分数分数可能需要特殊处理如去除末尾多余的零1.2 选择合适的数据结构在C中我们有多种方式可以表示学生数据// 方案1使用结构体数组 struct Student { int id; double score; }; Student students[100]; // 方案2使用vector容器 vectorStudent students;选择建议固定数量且已知上限时数组更简单直接数据量不确定或可能很大时vector更灵活安全2. 排序算法对比与选择2.1 手写排序算法实现我们先看看传统的排序方法如何解决这个问题// 冒泡排序实现 for(int i 0; i n-1; i) { for(int j 0; j n-i-1; j) { if(students[j].score students[j1].score) { swap(students[j], students[j1]); } } }性能分析时间复杂度O(n²)空间复杂度O(1)优点实现简单适合教学缺点效率低不适合大规模数据2.2 STL sort的优势相比之下STL的sort算法具有明显优势// 使用STL sort sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; // 降序排列 });关键优势时间复杂度O(n log n)效率显著提升代码简洁只需定义比较规则稳定性经过充分优化适合竞赛环境提示在竞赛编程中应优先使用标准库提供的算法避免重复造轮子这不仅能节省时间还能减少出错概率。3. 自定义排序规则的多种实现方式3.1 重载小于运算符在结构体内部重载运算符是最封装良好的方式struct Student { int id; double score; bool operator(const Student other) const { return score other.score; // 注意是降序 } }; // 使用时直接调用sort sort(students, students n);3.2 使用独立比较函数对于需要多种排序方式的情况独立函数更灵活bool compareStudents(const Student a, const Student b) { return a.score b.score; } // 使用时传入比较函数 sort(students.begin(), students.end(), compareStudents);3.3 Lambda表达式C11及以上现代C推荐使用lambda表达式尤其是一次性比较逻辑sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; });方法对比表方法适用场景优点缺点运算符重载固定排序规则调用简洁不够灵活独立函数多种排序需求可复用需要额外定义Lambda一次性使用灵活方便不能复用4. 完整解题流程与代码实现4.1 输入处理与边界检查良好的编程习惯应从输入处理开始int n, k; cin n k; if(k 1 || k n) { cerr Invalid k value endl; return 1; } vectorStudent students(n); for(int i 0; i n; i) { cin students[i].id students[i].score; }4.2 排序实现选择最优的排序方式// 使用lambda表达式实现降序排序 sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; });4.3 输出处理注意题目对输出格式的要求// 直接使用cout输出会自动处理浮点数格式 cout students[k-1].id students[k-1].score;注意vector下标从0开始所以第k名对应索引k-14.4 完整代码示例#include iostream #include vector #include algorithm using namespace std; struct Student { int id; double score; }; int main() { int n, k; cin n k; vectorStudent students(n); for(int i 0; i n; i) { cin students[i].id students[i].score; } sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; }); cout students[k-1].id students[k-1].score; return 0; }5. 调试技巧与常见问题5.1 常见错误排查下标越界忘记vector从0开始导致k-1可能为负排序方向错误降序写成升序浮点数比较直接使用比较浮点数可能不准确5.2 测试用例设计好的测试用例应覆盖各种边界情况最小规模n1, k1最大规模n100, k100极端值所有分数相同随机数据验证排序正确性示例测试数据// 测试数据1常规情况 5 3 1001 95.5 1002 88.0 1003 92.5 1004 90.0 1005 89.5 // 测试数据2所有分数相同 3 2 2001 85.0 2002 85.0 2003 85.0 // 测试数据3最小规模 1 1 3001 99.95.3 性能优化建议虽然这道题数据量不大但养成性能意识很重要使用reserve预先分配vector空间避免不必要的拷贝使用引用传参考虑使用更快的IO方式如scanf/printf或关闭同步// 提升IO速度的技巧 ios::sync_with_stdio(false); cin.tie(nullptr);6. 扩展思考与实际应用6.1 多条件排序实际问题中经常需要多级排序例如分数相同按学号升序sort(students.begin(), students.end(), [](const Student a, const Student b) { if(a.score ! b.score) return a.score b.score; return a.id b.id; });6.2 结构体设计进阶更复杂的数据结构设计struct ExamResult { int student_id; string name; double score; int rank; // 可以添加更多字段和方法 };6.3 STL算法的其他应用除了sort其他有用的算法// 查找特定分数段的学生 auto it find_if(students.begin(), students.end(), [](const Student s) { return s.score 90.0; }); // 统计及格人数 int pass_count count_if(students.begin(), students.end(), [](const Student s) { return s.score 60.0; });在实际竞赛中这类数据处理题目非常常见。掌握结构体和STL算法的组合使用可以大幅提升解题效率。我曾在一次模拟赛中遇到类似题目当时因为不熟悉sort的自定义比较而浪费了大量时间手写排序结果不仅代码冗长还引入了难以发现的bug。从那以后我深刻认识到标准库工具的重要性。
信息学奥赛刷题笔记：用C++结构体+STL sort搞定OpenJudge NOI 1.10 01排名查询
信息学奥赛刷题笔记用C结构体STL sort搞定OpenJudge NOI 1.10 01排名查询在信息学奥赛的备战过程中掌握高效的数据处理技巧至关重要。今天我们要探讨的是一道经典题目——OpenJudge NOI 1.10 01谁考了第k名这道题看似简单却蕴含着C编程中几个核心概念结构体定义、自定义排序规则以及STL算法的巧妙应用。对于初学者来说这道题提供了一个绝佳的机会让我们能够从读题-建模-实现-调试的完整解题流程中深入理解如何将实际问题转化为代码解决方案。更重要的是通过对比手写排序算法与STL sort的实现方式我们可以直观感受到标准库工具带来的代码简洁性和效率提升。1. 题目分析与数据结构建模1.1 理解题目需求题目要求我们处理一组学生数据每个学生有学号和分数两个属性需要根据分数从高到低排序后输出第k名学生的信息。看似简单的需求背后我们需要考虑几个关键点数据规模虽然示例数据量不大但竞赛中需要考虑效率排序规则降序排列分数高的在前输出格式学号和分数分数可能需要特殊处理如去除末尾多余的零1.2 选择合适的数据结构在C中我们有多种方式可以表示学生数据// 方案1使用结构体数组 struct Student { int id; double score; }; Student students[100]; // 方案2使用vector容器 vectorStudent students;选择建议固定数量且已知上限时数组更简单直接数据量不确定或可能很大时vector更灵活安全2. 排序算法对比与选择2.1 手写排序算法实现我们先看看传统的排序方法如何解决这个问题// 冒泡排序实现 for(int i 0; i n-1; i) { for(int j 0; j n-i-1; j) { if(students[j].score students[j1].score) { swap(students[j], students[j1]); } } }性能分析时间复杂度O(n²)空间复杂度O(1)优点实现简单适合教学缺点效率低不适合大规模数据2.2 STL sort的优势相比之下STL的sort算法具有明显优势// 使用STL sort sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; // 降序排列 });关键优势时间复杂度O(n log n)效率显著提升代码简洁只需定义比较规则稳定性经过充分优化适合竞赛环境提示在竞赛编程中应优先使用标准库提供的算法避免重复造轮子这不仅能节省时间还能减少出错概率。3. 自定义排序规则的多种实现方式3.1 重载小于运算符在结构体内部重载运算符是最封装良好的方式struct Student { int id; double score; bool operator(const Student other) const { return score other.score; // 注意是降序 } }; // 使用时直接调用sort sort(students, students n);3.2 使用独立比较函数对于需要多种排序方式的情况独立函数更灵活bool compareStudents(const Student a, const Student b) { return a.score b.score; } // 使用时传入比较函数 sort(students.begin(), students.end(), compareStudents);3.3 Lambda表达式C11及以上现代C推荐使用lambda表达式尤其是一次性比较逻辑sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; });方法对比表方法适用场景优点缺点运算符重载固定排序规则调用简洁不够灵活独立函数多种排序需求可复用需要额外定义Lambda一次性使用灵活方便不能复用4. 完整解题流程与代码实现4.1 输入处理与边界检查良好的编程习惯应从输入处理开始int n, k; cin n k; if(k 1 || k n) { cerr Invalid k value endl; return 1; } vectorStudent students(n); for(int i 0; i n; i) { cin students[i].id students[i].score; }4.2 排序实现选择最优的排序方式// 使用lambda表达式实现降序排序 sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; });4.3 输出处理注意题目对输出格式的要求// 直接使用cout输出会自动处理浮点数格式 cout students[k-1].id students[k-1].score;注意vector下标从0开始所以第k名对应索引k-14.4 完整代码示例#include iostream #include vector #include algorithm using namespace std; struct Student { int id; double score; }; int main() { int n, k; cin n k; vectorStudent students(n); for(int i 0; i n; i) { cin students[i].id students[i].score; } sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; }); cout students[k-1].id students[k-1].score; return 0; }5. 调试技巧与常见问题5.1 常见错误排查下标越界忘记vector从0开始导致k-1可能为负排序方向错误降序写成升序浮点数比较直接使用比较浮点数可能不准确5.2 测试用例设计好的测试用例应覆盖各种边界情况最小规模n1, k1最大规模n100, k100极端值所有分数相同随机数据验证排序正确性示例测试数据// 测试数据1常规情况 5 3 1001 95.5 1002 88.0 1003 92.5 1004 90.0 1005 89.5 // 测试数据2所有分数相同 3 2 2001 85.0 2002 85.0 2003 85.0 // 测试数据3最小规模 1 1 3001 99.95.3 性能优化建议虽然这道题数据量不大但养成性能意识很重要使用reserve预先分配vector空间避免不必要的拷贝使用引用传参考虑使用更快的IO方式如scanf/printf或关闭同步// 提升IO速度的技巧 ios::sync_with_stdio(false); cin.tie(nullptr);6. 扩展思考与实际应用6.1 多条件排序实际问题中经常需要多级排序例如分数相同按学号升序sort(students.begin(), students.end(), [](const Student a, const Student b) { if(a.score ! b.score) return a.score b.score; return a.id b.id; });6.2 结构体设计进阶更复杂的数据结构设计struct ExamResult { int student_id; string name; double score; int rank; // 可以添加更多字段和方法 };6.3 STL算法的其他应用除了sort其他有用的算法// 查找特定分数段的学生 auto it find_if(students.begin(), students.end(), [](const Student s) { return s.score 90.0; }); // 统计及格人数 int pass_count count_if(students.begin(), students.end(), [](const Student s) { return s.score 60.0; });在实际竞赛中这类数据处理题目非常常见。掌握结构体和STL算法的组合使用可以大幅提升解题效率。我曾在一次模拟赛中遇到类似题目当时因为不熟悉sort的自定义比较而浪费了大量时间手写排序结果不仅代码冗长还引入了难以发现的bug。从那以后我深刻认识到标准库工具的重要性。
