刷学校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::vectorStudent 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::vectorStudent students(n)是C11之后的写法会创建n个默认构造的Student对象然后逐个读入数据。如果OJ环境比较老不支持C11可以改成Student students[1005]这样的固定大小数组。第二cnt n 5 ? n : 5这个处理非常必要。很多题目数据保证n不小于5所以有人会直接写for (int i 0; i 5; i)一旦哪天遇到n3的边界数据就直接越界访问。基础题里养成“取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。结果有个测试点偏偏就n3程序虽然没崩但越界读取了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为何依赖严格弱序。这种“主动犯错”的训练方式比连做十道同样难度的题更能沉淀长期经验。
