刷学校OJ的基础题库时，有一道题让我记忆特别深——题号排在九十几，名字就叫“奖学金”。单看题面，它只是很普通的成绩排序：给你一批学生的学号、语文、数学、英语成绩，按“总分优先、语文次之、学号最后”的规则排出前几名。结果我却连交三次才完全通过，而且前两次挂得都挺丢人。后来我越琢磨越觉得，这道题几乎是为“多关键字排序”量身定制的入门题，把C++里结构体、sort、比较函数、边界条件这些基础功全串起来了。这篇文章就从头到尾把它拆一遍，适合刚学完结构体和排序、准备机考、或者正在刷基础题库的朋友参考。我会把完整可AC的写法给出来，也会把题目里那些“没人明说但有坑”的细节摊开讲清楚。1. 奖学金题的题面逻辑与核心考点1.1 输入输出格式到底长什么样这种题在各个OJ平台上的版本略有差异，但大体逻辑是一致的。常见输入格式是：第一行一个整数n，表示学生人数；接下来n行，每行四个整数，分别是学号、语文成绩、数学成绩、英语成绩。输出一般要求按排名输出前五名，每行一个学生，输出学号和总分，空格隔开。有的版本会把数学、英语换成别的科目，有的会在成绩后面加一个“德育分”之类的字段；但只要排序规则还是“总分优先、同分比语文、再同分比学号”，那核心解法就不会变。我一般会把输入样例先在本地跑一遍，再提交到OJ。很多同学直接跳过样例只看题面，其实样例里藏着不少信息——尤其是“学号是否要升序输出”“总分相同到底先比哪一科”，样例里基本都会体现。1.2 排序规则的三种等价理解方式“先按总分从高到低，总分相同按语文从高到低，语文也相同按学号从小到大。”这句话就是整道题的灵魂。第一种理解方式是最朴素的：定义一个大排序函数，里面依次比较总分、语文、学号。第二种理解方式是把它看成字典序的变体：如果把每个学生看成一个三元组（-总分，-语文，学号），那么目标就是让三元组按字典序从小到大排列。为什么取负号？因为“从高到低”等价于“取负号后的从小到低”。这种理解在某些语言里写起来很方便，但C++里直接用自定义比较函数更直白。第三种理解方式是“两两比较”：任何时候要判断学生A是否该排到学生B前面，就只看这三个条件。这个视角最贴近比较函数本身，也是写代码时唯一需要关心的。1.3 为什么这道题总能出现在基础题库因为它是典型的“复合排序”，难度刚刚好。只用冒泡排序也能做，但代码会写得比较啰嗦；用sort配合自定义比较函数，就能把“逻辑”和“排序算法”解耦，让初学者意识到：排序不一定非要自己从头实现，关键是定义清楚“谁在谁前面”。这道题还顺便考察了结构体的使用。有些人习惯开三个平行数组分别存学号、语文、总分，排序时手动交换三个数组；那样做也能通过，但代码的可读性和可维护性会差很多。结构体把学生的所有属性打包在一起，交换一次就是交换一个完整对象，这才符合正常的建模思维。2. 用结构体和自定义比较函数解决问题2.1 结构体设计：别让总分成为“临时计算项”我第一次写这题时，脑子一热，结构体里只存了学号、语文、数学、英语，总分每次比较的时候现算：a.Chinese + a.Math + a.English。代码能跑，但丑，而且容易出现低级错误，比如总分算错、类型溢出、重复计算的性能浪费。正确的做法是在读入每个学生数据后，立刻把总分算好存进结构体里。这样比较函数只需要读一个total字段，既快又清晰。#include <cstdio> #include <vector> #include <algorithm> struct Student { int id; int chinese; int math; int english; int total; };从设计角度讲，这个结构体把“一个学生”完整地表示了出来。如果后续要扩展——比如加一个“奖学金等级”字段，或者追加一门“实验成绩”——都只需要在结构体里加字段，排序逻辑几乎不受影响。2.2 cmp函数与严格弱序：sort的安全底线C++的std::sort要求比较函数满足“严格弱序”（strict weak ordering）。这句话听起来吓人，其实要记住的就一点：比较函数回答“a是否应该排在b前面”，当两个元素相等或等价时，必须返回false。最经典的错误是这样的：bool cmp(const Student& a, const Student& b) { if (a.total != b.total) { return a.total > b.total; } if (a.chinese != b.chinese) { return a.chinese > b.chinese; } return a.id >= b.id; // 错误：相等时返回true }当两个学生连学号都相同时（理论上不会发生，但逻辑上存在这种可能），这个函数在a和b上会返回true，在b和a上也会返回true。sort内部一旦发现“a排在b前面”且“b排在a前面”，整个排序结果就会乱掉，轻则输出顺序不对，重则在特定数据下崩溃。所以写比较函数的铁律是：相等的情况永远返回false，只写<或>，别写>=或<=。对于学号升序，写a.id < b.id，不写a.id <= b.id。2.3 完整可AC的代码和逐行说明下面这段代码是我最终提交的版本，输入输出用scanf/printf而不是cin/cout，纯粹是习惯问题，在基础题里两者都不太可能超时。#include <cstdio> #include <vector> #include <algorithm> struct Student { int id; int chinese; int math; int english; int total; }; bool cmp(const Student& a, const Student& b) { if (a.total != b.total) { return a.total > b.total; // 第一关键字：总分降序 } if (a.chinese != b.chinese) { return a.chinese > b.chinese; // 第二关键字：语文降序 } return a.id < b.id; // 第三关键字：学号升序 } int main() { int n; scanf("%d", &n); std::vector<Student> students(n); for (int i = 0; i < n; ++i) { scanf("%d%d%d%d", &students[i].id, &students[i].chinese, &students[i].math, &students[i].english); students[i].total = students[i].chinese + students[i].math + students[i].english; } std::sort(students.begin(), students.end(), cmp); int cnt = n < 5 ? n : 5; // 不足5人时全部输出 for (int i = 0; i < cnt; ++i) { printf("%d %d\n", students[i].id, students[i].total); } return 0; }这里有两个细节值得强调。第一，std::vector<Student> students(n)是C++11之后的写法，会创建n个默认构造的Student对象，然后逐个读入数据。如果OJ环境比较老，不支持C++11，可以改成Student students[1005]这样的固定大小数组。第二，cnt = n < 5 ? n : 5这个处理非常必要。很多题目数据保证n不小于5，所以有人会直接写for (int i = 0; i < 5; ++i)，一旦哪天遇到n=3的边界数据就直接越界访问。基础题里养成“取min”的习惯，后面做大题会少踩很多坑。2.4 三种排序写法的取舍：不止一种AC姿势除了自定义cmp配合sort，这道题还有另外两种常见写法。第一种是重载小于运算符：bool operator<(const Student& a, const Student& b) { if (a.total != b.total) return a.total > b.total; if (a.chinese != b.chinese) return a.chinese > b.chinese; return a.id < b.id; }然后直接std::sort(students.begin(), students.end())。这种写法的好处是“一个学生怎么比”这件事直接被固化进类型里，以后任何地方排序都不需要再传cmp。坏处是如果你对同一个类型有不同的排序需求（比如按数学成绩排），重载运算符就不够灵活，还得绕回去写cmp。第二种是stable_sort逐级排序：std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) { return a.id < b.id; }); std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) { return a.chinese > b.chinese; }); std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) { return a.total > b.total; });思路很巧妙：先用学号升序排一次，再用语文降序稳定排，最后用总分降序稳定排。stable_sort的“稳定”保证了每次排序都不会打乱上一次排序建立的相对顺序。最终效果和一次性cmp完全一致。但这种写法有个前提逻辑：最后一次是关键优先级最高的关键字，最早排的是优先级最低的关键字。很多人一上来就把顺序搞反，结果排完发现和预期正好反了。我建议刚开始刷题时直接用cmp，等彻底理解了稳定性，再尝试这种花式写法。3. 我连交三次才过的那些坑3.1 比较函数里的“等于”是隐形炸弹我第一次提交，就是把学号比较写成了return a.id >= b.id。样例数据里所有学号都不同，所以样例顺利通过；一旦遇到有两个学生总分、语文都相同的情况，排序顺序就开始随机，五个学生里有三个位置错乱，直接WA。这个教训让我明白了一个道理：OJ的样例覆盖不了所有数据组合。比较函数不是“样例没过才改”，而是要自问一句：当两个元素在前两个关键字上都相等时，我的第三关键字能给出唯一确定的结果吗？检查方法很简单：把cmp函数里的每个分支都试想一遍，a和b完全相等时返回什么？如果返回了true，立刻改掉。3.2 语文降序和学号升序的方向容易写反第二关键字是语文从高到低，所以是a.chinese > b.chinese；第三关键字是学号从低到高，所以是a.id < b.id。这两个方向相反，特别容易手滑。我的记忆方法是把不等号读数读出来：>表示“大的排前面”，<表示“小的排前面”。先看题目要求“高分的在前”还是“低分的在前”，再决定符号。别凭感觉写，写完回头把这三个分支大声念一遍：“总分大的在前；总分相同则语文大的在前；语文也相同则学号小的在前。”念完就知道符号对不对。3.3 前五名的输出边界：n小于5时不越界第二次提交WA的原因不是排序，而是我直接写死了for (int i = 0; i < 5; ++i)。当时觉得题目都说“评选奖学金”，怎么可能人数少于5。结果有个测试点偏偏就n=3，程序虽然没崩，但越界读取了vector后面未初始化的内存，输出了几个乱码数字。从此我养成了一个习惯：凡是从一个集合里取“前k个”，一律先判断集合大小和k的大小关系。代码里写int cnt = n < 5 ? n : 5;或者int cnt = std::min(n, 5);，一劳永逸。3.4 空白字符：scanf永远比你想的更宽容有同学用cin读int，遇到换行或空格都没问题；但如果你混用scanf和getchar，就很容易踩中“读到了多余换行”的坑。比如有人想用getchar把每行末尾的换行吃掉，结果吃掉了下一行的负数符号或数字第一位，程序直接读入错误数据。我忠告是：读纯数字序列，只用scanf或cin，完全不需要手动处理换行符，它们会自动跳过空白字符。省下的精力足够多检查两遍比较函数了。4. 只取前五名的优化：局部排序与堆思路4.1 这题真的需要优化吗？先说结论：如果n不超过几千，sort全排是绝对够用的，没必要瞎折腾。奖学金这道题在绝大多数OJ平台上n都在几千以内，O(n log n)的sort跑起来感觉不到任何耗时。但“只取前五名”这个条件确实给了我们一个优化空间。假设某天n变成了十万甚至百万，目标只是要排名最靠前的5个人，全排序的时间复杂度是O(n log n)，而理论下限应该是O(n log 5)，也就是O(n)。当n足够大时，这个差距是实实在在的。4.2 partial_sort：一个函数解决“部分有序”C++标准库提供了一个很方便的算法叫std::partial_sort，它接受三个迭代器：first、middle、last。调用结束后，[first, middle)范围内存放的是整个范围内“按cmp排序后最小的那一批元素”，且这批元素内部已经有序；后面的元素顺序则不保证。放在这道题里，就是：int k = std::min(n, 5); std::partial_sort(students.begin(), students.begin() + k, students.end(), cmp); for (int i = 0; i < k; ++i) { printf("%d %d\n", students[i].id, students[i].total); }注意cmp的定义还是“总分高排前面”，所以partial_sort放在开头的正是总分最高的k个人。我在本地拿一亿条随机数据测过一次，partial_sort比全排快了不止一个数量级，内存占用也差不多。作为扩展知识点，这个函数值得记住；但写题过程中如果n很小，正常sort就完了。4.3 自己维护大小为5的容器也可以如果你完全不用STL，还有一个手写的思路：维护一个大小为5的数组，初始放前5个学生，每次来一个新学生，就在这5个里找到排名最低的那个，如果新学生比它排名高就替换。这样一趟扫过去只需要O(n*5)，本质上是“选择排序”的变体。但我不推荐在基础题阶段这么写，原因很简单：逻辑紧凑容易出错，而且还要处理n不到5的情况。用sort或partial_sort，代码更清晰，出错的概率更低。除非你正在学习“如何手写TopK”，否则没必要给自己加戏。5. 从奖学金题延伸出来的普适排序经验5.1 一个通用的多关键字比较模板奖学金题解决之后，我把这类问题抽象成了一个模板，后面遇到任何“按多个字段排名”的需求，直接往里套：bool cmp(const Item& a, const Item& b) { // 从优先级最高的关键字开始，逐级判断 if (a.key1 != b.key1) { return a.key1 > b.key1; // 把实际升降序规则填在这里 } if (a.key2 != b.key2) { return a.key2 > b.key2; } // 最后一个关键字：建议总有一个唯一标识字段（如id）来兜底 return a.id < b.id; }这套模板有一个额外的好处：最后一个“兜底字段”可以让排序结果变成完全确定的。即使前面所有关键字都相等，也能稳定地决定先后顺序，杜绝随机性。在OJ排错时，一个“每次运行结果都一致”的程序，debug难度会显著降低。5.2 同一题的不同版本怎么快速迁移东华OJ的96题是个基础版，但其他OJ平台有进阶版：有的要求输出“所有获得奖学金的学生”，名额不再是固定的5，而是“总分不低于某个分数线”；有的要求额外输出各科平均分；有的把学号换成了字符串，甚至换成了包含字母的“准考证号”。碰到这些变体，处理思路完全一样：第一，搞清楚排序的优先级；第二，把额外的输出字段加进结构体；第三，改输出格式。至于排序核心，几乎可以原封不动搬过去。字符串学号的比较稍微注意一下，用std::string直接支持<和>比较，或者用C风格字符串的strcmp。5.3 机考和面试里识别排序题的方式很多人觉得这类题太简单，不屑于复盘。但实际机考中，排序题常被包装成“统计前几名”“找出排行榜前K人”“筛选满足条件并按规则输出”。识别方法就一句话：只要题目里出现“按XX排序、再按XX排序、取前几位”，不管描述得多么花哨，底子大概率还是多关键字排序加TopK。我的个人习惯是：先把比较规则用中文写在草稿纸或注释里，再翻译成cmp代码。中文写“总分从高到低”，代码就是a.total > b.total；中文写“学号从低到高”，代码就是a.id < b.id。看着注释写代码，比对着题面来回翻快得多，也少犯方向性错误。最后再说一个我自己的小技巧：刷这类基础题时，做完AC之后别急着看下一题，花五分钟把cmp函数里的条件调换顺序，故意写错一版再提交一次，观察WA的输出，能帮助你理解sort为何依赖严格弱序。这种“主动犯错”的训练方式，比连做十道同样难度的题更能沉淀长期经验。
刷学校OJ的基础题库时，有一道题让我记忆特别深——题号排在九十几，名字就叫“奖学金”。单看题面，它只是很普通的成绩排序：给你一批学生的学号、语文、数学、英语成绩，按“总分优先、语文次之、学号最后”的规则排出前几名。结果我却连交三次才完全通过，而且前两次挂得都挺丢人。后来我越琢磨越觉得，这道题几乎是为“多关键字排序”量身定制的入门题，把C++里结构体、sort、比较函数、边界条件这些基础功全串起来了。这篇文章就从头到尾把它拆一遍，适合刚学完结构体和排序、准备机考、或者正在刷基础题库的朋友参考。我会把完整可AC的写法给出来，也会把题目里那些“没人明说但有坑”的细节摊开讲清楚。1. 奖学金题的题面逻辑与核心考点1.1 输入输出格式到底长什么样这种题在各个OJ平台上的版本略有差异，但大体逻辑是一致的。常见输入格式是：第一行一个整数n，表示学生人数；接下来n行，每行四个整数，分别是学号、语文成绩、数学成绩、英语成绩。输出一般要求按排名输出前五名，每行一个学生，输出学号和总分，空格隔开。有的版本会把数学、英语换成别的科目，有的会在成绩后面加一个“德育分”之类的字段；但只要排序规则还是“总分优先、同分比语文、再同分比学号”，那核心解法就不会变。我一般会把输入样例先在本地跑一遍，再提交到OJ。很多同学直接跳过样例只看题面，其实样例里藏着不少信息——尤其是“学号是否要升序输出”“总分相同到底先比哪一科”，样例里基本都会体现。1.2 排序规则的三种等价理解方式“先按总分从高到低，总分相同按语文从高到低，语文也相同按学号从小到大。”这句话就是整道题的灵魂。第一种理解方式是最朴素的：定义一个大排序函数，里面依次比较总分、语文、学号。第二种理解方式是把它看成字典序的变体：如果把每个学生看成一个三元组（-总分，-语文，学号），那么目标就是让三元组按字典序从小到大排列。为什么取负号？因为“从高到低”等价于“取负号后的从小到低”。这种理解在某些语言里写起来很方便，但C++里直接用自定义比较函数更直白。第三种理解方式是“两两比较”：任何时候要判断学生A是否该排到学生B前面，就只看这三个条件。这个视角最贴近比较函数本身，也是写代码时唯一需要关心的。1.3 为什么这道题总能出现在基础题库因为它是典型的“复合排序”，难度刚刚好。只用冒泡排序也能做，但代码会写得比较啰嗦；用sort配合自定义比较函数，就能把“逻辑”和“排序算法”解耦，让初学者意识到：排序不一定非要自己从头实现，关键是定义清楚“谁在谁前面”。这道题还顺便考察了结构体的使用。有些人习惯开三个平行数组分别存学号、语文、总分，排序时手动交换三个数组；那样做也能通过，但代码的可读性和可维护性会差很多。结构体把学生的所有属性打包在一起，交换一次就是交换一个完整对象，这才符合正常的建模思维。2. 用结构体和自定义比较函数解决问题2.1 结构体设计：别让总分成为“临时计算项”我第一次写这题时，脑子一热，结构体里只存了学号、语文、数学、英语，总分每次比较的时候现算：a.Chinese + a.Math + a.English。代码能跑，但丑，而且容易出现低级错误，比如总分算错、类型溢出、重复计算的性能浪费。正确的做法是在读入每个学生数据后，立刻把总分算好存进结构体里。这样比较函数只需要读一个total字段，既快又清晰。#include <cstdio> #include <vector> #include <algorithm> struct Student { int id; int chinese; int math; int english; int total; };从设计角度讲，这个结构体把“一个学生”完整地表示了出来。如果后续要扩展——比如加一个“奖学金等级”字段，或者追加一门“实验成绩”——都只需要在结构体里加字段，排序逻辑几乎不受影响。2.2 cmp函数与严格弱序：sort的安全底线C++的std::sort要求比较函数满足“严格弱序”（strict weak ordering）。这句话听起来吓人，其实要记住的就一点：比较函数回答“a是否应该排在b前面”，当两个元素相等或等价时，必须返回false。最经典的错误是这样的：bool cmp(const Student& a, const Student& b) { if (a.total != b.total) { return a.total > b.total; } if (a.chinese != b.chinese) { return a.chinese > b.chinese; } return a.id >= b.id; // 错误：相等时返回true }当两个学生连学号都相同时（理论上不会发生，但逻辑上存在这种可能），这个函数在a和b上会返回true，在b和a上也会返回true。sort内部一旦发现“a排在b前面”且“b排在a前面”，整个排序结果就会乱掉，轻则输出顺序不对，重则在特定数据下崩溃。所以写比较函数的铁律是：相等的情况永远返回false，只写<或>，别写>=或<=。对于学号升序，写a.id < b.id，不写a.id <= b.id。2.3 完整可AC的代码和逐行说明下面这段代码是我最终提交的版本，输入输出用scanf/printf而不是cin/cout，纯粹是习惯问题，在基础题里两者都不太可能超时。#include <cstdio> #include <vector> #include <algorithm> struct Student { int id; int chinese; int math; int english; int total; }; bool cmp(const Student& a, const Student& b) { if (a.total != b.total) { return a.total > b.total; // 第一关键字：总分降序 } if (a.chinese != b.chinese) { return a.chinese > b.chinese; // 第二关键字：语文降序 } return a.id < b.id; // 第三关键字：学号升序 } int main() { int n; scanf("%d", &n); std::vector<Student> students(n); for (int i = 0; i < n; ++i) { scanf("%d%d%d%d", &students[i].id, &students[i].chinese, &students[i].math, &students[i].english); students[i].total = students[i].chinese + students[i].math + students[i].english; } std::sort(students.begin(), students.end(), cmp); int cnt = n < 5 ? n : 5; // 不足5人时全部输出 for (int i = 0; i < cnt; ++i) { printf("%d %d\n", students[i].id, students[i].total); } return 0; }这里有两个细节值得强调。第一，std::vector<Student> students(n)是C++11之后的写法，会创建n个默认构造的Student对象，然后逐个读入数据。如果OJ环境比较老，不支持C++11，可以改成Student students[1005]这样的固定大小数组。第二，cnt = n < 5 ? n : 5这个处理非常必要。很多题目数据保证n不小于5，所以有人会直接写for (int i = 0; i < 5; ++i)，一旦哪天遇到n=3的边界数据就直接越界访问。基础题里养成“取min”的习惯，后面做大题会少踩很多坑。2.4 三种排序写法的取舍：不止一种AC姿势除了自定义cmp配合sort，这道题还有另外两种常见写法。第一种是重载小于运算符：bool operator<(const Student& a, const Student& b) { if (a.total != b.total) return a.total > b.total; if (a.chinese != b.chinese) return a.chinese > b.chinese; return a.id < b.id; }然后直接std::sort(students.begin(), students.end())。这种写法的好处是“一个学生怎么比”这件事直接被固化进类型里，以后任何地方排序都不需要再传cmp。坏处是如果你对同一个类型有不同的排序需求（比如按数学成绩排），重载运算符就不够灵活，还得绕回去写cmp。第二种是stable_sort逐级排序：std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) { return a.id < b.id; }); std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) { return a.chinese > b.chinese; }); std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) { return a.total > b.total; });思路很巧妙：先用学号升序排一次，再用语文降序稳定排，最后用总分降序稳定排。stable_sort的“稳定”保证了每次排序都不会打乱上一次排序建立的相对顺序。最终效果和一次性cmp完全一致。但这种写法有个前提逻辑：最后一次是关键优先级最高的关键字，最早排的是优先级最低的关键字。很多人一上来就把顺序搞反，结果排完发现和预期正好反了。我建议刚开始刷题时直接用cmp，等彻底理解了稳定性，再尝试这种花式写法。3. 我连交三次才过的那些坑3.1 比较函数里的“等于”是隐形炸弹我第一次提交，就是把学号比较写成了return a.id >= b.id。样例数据里所有学号都不同，所以样例顺利通过；一旦遇到有两个学生总分、语文都相同的情况，排序顺序就开始随机，五个学生里有三个位置错乱，直接WA。这个教训让我明白了一个道理：OJ的样例覆盖不了所有数据组合。比较函数不是“样例没过才改”，而是要自问一句：当两个元素在前两个关键字上都相等时，我的第三关键字能给出唯一确定的结果吗？检查方法很简单：把cmp函数里的每个分支都试想一遍，a和b完全相等时返回什么？如果返回了true，立刻改掉。3.2 语文降序和学号升序的方向容易写反第二关键字是语文从高到低，所以是a.chinese > b.chinese；第三关键字是学号从低到高，所以是a.id < b.id。这两个方向相反，特别容易手滑。我的记忆方法是把不等号读数读出来：>表示“大的排前面”，<表示“小的排前面”。先看题目要求“高分的在前”还是“低分的在前”，再决定符号。别凭感觉写，写完回头把这三个分支大声念一遍：“总分大的在前；总分相同则语文大的在前；语文也相同则学号小的在前。”念完就知道符号对不对。3.3 前五名的输出边界：n小于5时不越界第二次提交WA的原因不是排序，而是我直接写死了for (int i = 0; i < 5; ++i)。当时觉得题目都说“评选奖学金”，怎么可能人数少于5。结果有个测试点偏偏就n=3，程序虽然没崩，但越界读取了vector后面未初始化的内存，输出了几个乱码数字。从此我养成了一个习惯：凡是从一个集合里取“前k个”，一律先判断集合大小和k的大小关系。代码里写int cnt = n < 5 ? n : 5;或者int cnt = std::min(n, 5);，一劳永逸。3.4 空白字符：scanf永远比你想的更宽容有同学用cin读int，遇到换行或空格都没问题；但如果你混用scanf和getchar，就很容易踩中“读到了多余换行”的坑。比如有人想用getchar把每行末尾的换行吃掉，结果吃掉了下一行的负数符号或数字第一位，程序直接读入错误数据。我忠告是：读纯数字序列，只用scanf或cin，完全不需要手动处理换行符，它们会自动跳过空白字符。省下的精力足够多检查两遍比较函数了。4. 只取前五名的优化：局部排序与堆思路4.1 这题真的需要优化吗？先说结论：如果n不超过几千，sort全排是绝对够用的，没必要瞎折腾。奖学金这道题在绝大多数OJ平台上n都在几千以内，O(n log n)的sort跑起来感觉不到任何耗时。但“只取前五名”这个条件确实给了我们一个优化空间。假设某天n变成了十万甚至百万，目标只是要排名最靠前的5个人，全排序的时间复杂度是O(n log n)，而理论下限应该是O(n log 5)，也就是O(n)。当n足够大时，这个差距是实实在在的。4.2 partial_sort：一个函数解决“部分有序”C++标准库提供了一个很方便的算法叫std::partial_sort，它接受三个迭代器：first、middle、last。调用结束后，[first, middle)范围内存放的是整个范围内“按cmp排序后最小的那一批元素”，且这批元素内部已经有序；后面的元素顺序则不保证。放在这道题里，就是：int k = std::min(n, 5); std::partial_sort(students.begin(), students.begin() + k, students.end(), cmp); for (int i = 0; i < k; ++i) { printf("%d %d\n", students[i].id, students[i].total); }注意cmp的定义还是“总分高排前面”，所以partial_sort放在开头的正是总分最高的k个人。我在本地拿一亿条随机数据测过一次，partial_sort比全排快了不止一个数量级，内存占用也差不多。作为扩展知识点，这个函数值得记住；但写题过程中如果n很小，正常sort就完了。4.3 自己维护大小为5的容器也可以如果你完全不用STL，还有一个手写的思路：维护一个大小为5的数组，初始放前5个学生，每次来一个新学生，就在这5个里找到排名最低的那个，如果新学生比它排名高就替换。这样一趟扫过去只需要O(n*5)，本质上是“选择排序”的变体。但我不推荐在基础题阶段这么写，原因很简单：逻辑紧凑容易出错，而且还要处理n不到5的情况。用sort或partial_sort，代码更清晰，出错的概率更低。除非你正在学习“如何手写TopK”，否则没必要给自己加戏。5. 从奖学金题延伸出来的普适排序经验5.1 一个通用的多关键字比较模板奖学金题解决之后，我把这类问题抽象成了一个模板，后面遇到任何“按多个字段排名”的需求，直接往里套：bool cmp(const Item& a, const Item& b) { // 从优先级最高的关键字开始，逐级判断 if (a.key1 != b.key1) { return a.key1 > b.key1; // 把实际升降序规则填在这里 } if (a.key2 != b.key2) { return a.key2 > b.key2; } // 最后一个关键字：建议总有一个唯一标识字段（如id）来兜底 return a.id < b.id; }这套模板有一个额外的好处：最后一个“兜底字段”可以让排序结果变成完全确定的。即使前面所有关键字都相等，也能稳定地决定先后顺序，杜绝随机性。在OJ排错时，一个“每次运行结果都一致”的程序，debug难度会显著降低。5.2 同一题的不同版本怎么快速迁移东华OJ的96题是个基础版，但其他OJ平台有进阶版：有的要求输出“所有获得奖学金的学生”，名额不再是固定的5，而是“总分不低于某个分数线”；有的要求额外输出各科平均分；有的把学号换成了字符串，甚至换成了包含字母的“准考证号”。碰到这些变体，处理思路完全一样：第一，搞清楚排序的优先级；第二，把额外的输出字段加进结构体；第三，改输出格式。至于排序核心，几乎可以原封不动搬过去。字符串学号的比较稍微注意一下，用std::string直接支持<和>比较，或者用C风格字符串的strcmp。5.3 机考和面试里识别排序题的方式很多人觉得这类题太简单，不屑于复盘。但实际机考中，排序题常被包装成“统计前几名”“找出排行榜前K人”“筛选满足条件并按规则输出”。识别方法就一句话：只要题目里出现“按XX排序、再按XX排序、取前几位”，不管描述得多么花哨，底子大概率还是多关键字排序加TopK。我的个人习惯是：先把比较规则用中文写在草稿纸或注释里，再翻译成cmp代码。中文写“总分从高到低”，代码就是a.total > b.total；中文写“学号从低到高”，代码就是a.id < b.id。看着注释写代码，比对着题面来回翻快得多，也少犯方向性错误。最后再说一个我自己的小技巧：刷这类基础题时，做完AC之后别急着看下一题，花五分钟把cmp函数里的条件调换顺序，故意写错一版再提交一次，观察WA的输出，能帮助你理解sort为何依赖严格弱序。这种“主动犯错”的训练方式，比连做十道同样难度的题更能沉淀长期经验。