谁拿了最多奖学金：OJ经典题中的条件判断与边界处理

但凡刷过一点在线评测系统的人大概率都见过“谁拿了最多奖学金”这道题。它常挂在各类OJ入门题单里题号往往就是1269出处是NOIP 2005普及组第一题。别看它标注难度不高很多新手第一次提交照样会栽跟头WA得莫名其妙。这道题真正考的不是高深的算法而是三件看起来很简单、做起来却容易翻车的事条件判断的完整性、输入数据的处理方式、以及“只在必要时保存数据”的程序设计意识。今天我就把这道题从头到尾拆一遍从题目背景、思路选型到代码实现、踩坑记录全部铺开。不管是刚接触结构体排序的初学者还是想帮学弟学妹讲题的学长学姐这篇文章应该都能给你一些能直接拿去用的东西。1. 题目到底在考什么1.1 五个奖学金条件的来源与规则“谁拿了最多奖学金”这个题目背景是学校评选奖学金每个学生有五个评选维度每个维度对应一笔钱院士奖学金期末平均成绩高于80分并且在读期间发表论文不少于1篇奖励8000元。五四奖学金期末平均成绩高于85分并且班级评议成绩高于80分奖励4000元。成绩优秀奖期末平均成绩高于90分奖励2000元。西部奖学金期末平均成绩高于85分并且来自西部省份奖励1000元。班级贡献奖班级评议成绩高于80分并且担任班级干部奖励850元。输入数据里每个学生包含七个字段姓名、期末平均成绩、班级评议成绩、是否班干部Y/N、是否西部省份学生Y/N、发表论文数。要求输出三行获得奖学金总数最多的学生姓名、该学生的奖学金总数、所有学生奖学金总数的总和。这道题的背景虽然设定在校园但本质上是一个典型的多条件筛选与聚合计算问题。放在竞赛场景里它就是用来检验选手能不能把文字描述准确翻译成代码逻辑能不能把“满足多个条件才累加奖金”这件事处理干净。1.2 题目的难度定位与常见误判很多人一看题就觉得太简单了五个if就结束了。但实际评测结果往往会给这些人一记响亮的耳光。这道题的难点不在于“会不会用排序”而在于“能不能一次把所有细节都照顾到”。我从辅导新手的经历里观察到最常见的翻车点有三个把“高于80”写成“大于等于80”边界的等号搞错。读入“是否是班干部”和“是否是西部学生”时用字符类型没有处理好读到换行或空格。只记录每一笔奖金最后忘了累加总额或者总额的变量类型用得不对。另外还有一个逻辑层面的坑题目要求输出“获得最多奖学金的学生”如果存在并列应该输出在最前面出现的那个人。这一点在原题描述里其实有隐含约定但很多人会在排序方案里把并列情况处理反了。所以这道题真正考察的是你能不能像一台严谨的机器一样把条件逐条读透、逐条实现而不是炫技。算法复杂度要求在这里几乎不构成压力N最大也就100O(N)甚至O(N log N)都能过但前提是逻辑正确。2. 解题思路两种方案的取舍2.1 方案一把学生信息存进结构体再做排序很多初学者看到“谁最多”这种字眼第一反应是建一个结构体数组把所有学生的信息读进来然后写一个cmp函数按奖学金金额从大到小排序排完输出第一个。struct Student { string name; int avgScore; int classScore; char isLeader; char isWest; int papers; int money; };这个思路本身没有错也能过。但它引入了一些不必要的风险。排序意味着你要为结构体写比较器要把奖学金先算出来再排序还要考虑并列时保持输入顺序的问题。一旦比较器写得不够严谨比如奖学金相等时返回了false或者true的方向不对结果就会错。而且从程序效率的角度看排序是完全没有必要的。题目只关心“最大值”和“总和”这些都是可以在读入过程中同步维护的不需要把所有学生都存下来。排序不仅多写了代码还凭空增加了出错的空间。2.2 方案二边读边算维护最大值和总额更干净的做法是这样每读入一个学生的数据立刻用五个if计算他获得的奖学金总数。然后做两件事把这个数累加进总额变量。如果这个数大于当前记录的最大值就更新最大值并把当前学生的姓名记录下来。整个过程只需要一个循环不需要结构体数组不需要排序内存占用是常数级别。代码结构也非常清晰读数据、算钱、比较、更新四步一气呵成。int main() { int n; cin n; int total 0; int maxMoney 0; string maxName; for (int i 0; i n; i) { string name, leader, west; int avg, cls, papers; cin name avg cls leader west papers; int money 0; if (avg 80 papers 1) money 8000; if (avg 85 cls 80) money 4000; if (avg 90) money 2000; if (avg 85 west Y) money 1000; if (cls 80 leader Y) money 850; total money; if (money maxMoney) { maxMoney money; maxName name; } } cout maxName endl; cout maxMoney endl; cout total endl; return 0; }2.3 为什么“读入即处理”是更好的选择从软件工程的角度看“边读边算”体现的是一种流式处理思想数据不需要完整驻留内存读完一条就处理一条处理完就能丢弃。这种思想在真实开发里非常常见比如处理日志文件、统计流式数据等场景数据量可能大到你根本没法全部塞进内存但你只需要一个累加器和一个最大值变量就能完成任务。在这道题里N最大只有100用哪种方案性能上没有任何差别。但我要强调的不是性能而是“思维负担”。边读边算把“计算奖学金”和“寻找最大”这两件事紧紧耦合在一次遍历里你不需要额外维护一个结构体数组与排序后的索引关系也不需要担心比较器写错。代码量更少心智负担更低对新手来说绝对是首选。如果你以后做到类似的题目不妨先问自己一句我真的需要把所有数据都存下来吗很多时候答案是不需要。这个习惯能帮你省掉很多不必要的麻烦。3. 完整代码实现与逐行解析3.1 核心代码与变量设计我用C写了一个完整版本并且加了注释方便对照阅读。#include iostream using namespace std; int main() { int n; cin n; int totalMoney 0; // 所有学生奖学金总额 int maxMoney 0; // 当前最高奖学金数额 string maxName; // 当前最高奖学金学生姓名 for (int i 0; i n; i) { string name; int avgScore, classScore, paperCount; string isLeader, isWest; cin name avgScore classScore isLeader isWest paperCount; int money 0; // 1. 院士奖学金期末平均成绩 80论文数 1 if (avgScore 80 paperCount 1) { money 8000; } // 2. 五四奖学金期末平均成绩 85班级评议成绩 80 if (avgScore 85 classScore 80) { money 4000; } // 3. 成绩优秀奖期末平均成绩 90 if (avgScore 90) { money 2000; } // 4. 西部奖学金期末平均成绩 85是西部学生 if (avgScore 85 isWest Y) { money 1000; } // 5. 班级贡献奖班级评议成绩 80是班干部 if (classScore 80 isLeader Y) { money 850; } totalMoney money; if (money maxMoney) { maxMoney money; maxName name; } } cout maxName endl; cout maxMoney endl; cout totalMoney endl; return 0; }这里我刻意把“是否班干部”和“是否西部学生”都用string类型读入而不是用char。原因后面会专门讲这是一个很重要的实战细节。3.2 输入输出格式里容易被忽略的细节这道题的数据输入格式是一行一个学生字段之间用空格隔开。比如4 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1第一行是学生人数N之后N行每行依次是姓名、期末平均成绩、班级评议成绩、是否班干部、是否西部学生、论文数。用cin 连续读取可以自动跳过空白字符包括空格和换行所以不需要专门处理换行符。但需要注意如果你使用getline读整行然后再拆分就必须格外小心每行末尾的换行符和前面的残留字符。输出的时候要严格按照题目要求先输出最大学奖学金获得者的姓名再输出该学生的奖学金数最后输出总额每行一个数。很多人因为输出顺序搞反样例过不了白白丢分。3.3 手算一遍样例验证逻辑我们来把样例数据完整算一遍确认代码逻辑能和手算结果对上。第一个学生YaoLin平均87评议82班干部Y西部N论文0。院士奖学金平均87大于80但论文0篇不满足大于等于1所以不发放。五四奖学金平均87大于85评议82大于80发放4000。成绩优秀奖87不大于90不发放。西部奖学金平均87大于85但西部标记为N不发放。班级贡献奖评议82大于80班干部标记为Y发放850。YaoLin总额4850。第二个学生ChenRuiyi平均88评议78班干部N西部Y论文1。院士奖学金88大于80且论文1篇发放8000。五四奖学金平均88大于85但评议78不大于80不发放。成绩优秀奖88不大于90不发放。西部奖学金88大于85西部Y发放1000。班级贡献奖评议78不大于80不发放。ChenRuiyi总额9000。第三个学生LiXin平均92评议88班干部N西部N论文0。院士奖学金论文0不发放。五四奖学金92大于85评议88大于80发放4000。成绩优秀奖92大于90发放2000。西部奖学金不是西部学生不发放。班级贡献奖不是班干部不发放。LiXin总额6000。第四个学生ZhangQin平均83评议87班干部Y西部N论文1。院士奖学金83大于80论文1发放8000。五四奖学金83不大于85不发放。成绩优秀奖83不大于90不发放。西部奖学金83不大于85不发放。班级贡献奖评议87大于80班干部Y发放850。ZhangQin总额8850。总额等于4850加9000加6000加8850一共28700。最高奖学金获得者ChenRuiyi金额9000。这个结果与题目样例输出完全一致说明五个条件和累加逻辑都没有问题。4. 新手最容易踩的坑4.1 字符读入的经典翻车现场有些选手喜欢用char类型接收“是否班干部”和“是否西部学生”这两个字段。本身这么做没问题但坑在于后续比较。假如你写的是char leader, west; cin name avg cls leader west papers; if (cls 80 leader Y) ...这样写其实也能正常通过。真正出问题的是另一种写法先用cin读完整数然后再想用scanf或者getchar去读字符结果把上一行末尾的换行符给读了进去造成数据错位。我见过最典型的错误是有人用getline逐行读然后手动拆字符串。一旦某一行学生没有班干部标记或者论文数没跟上整个解析就乱套了。对这种固定格式的OJ输入最稳妥的方式就是让cin的流运算符自己去处理空白字符不要手动介入。为了避免麻烦我个人习惯把“是否”这类字段统一用string去接。程序读起来也更自然和Y字符串比较比和字符比较更容易让人理解而且完全不需要担心类型不匹配的问题。4.2 边界条件大于还是大于等于题目里的“高于80分”是大于80不是大于等于80。这个细节很多人第一次看会忽略但只要你少写一个等号遇到恰好80分的情况就会给出错误判断。整理一下边界的正确写法条件正确写法期末平均成绩高于80avg 80班级评议成绩高于80cls 80期末平均成绩高于85avg 85期末平均成绩高于90avg 90发表论文不少于1篇papers 1有个小技巧是题目描述里的“高于”“大于”都对应严格大于“不少于”“至少”对应大于等于。把中文关键词和运算符号做一个映射记忆基本不会错。4.3 最大值的初始化和并列情况的处理最大值变量初始化为0是没有问题的因为每个学生的奖学金总额只会是非负数。第一次循环如果money大于0自然能更新maxMoney。但如果你初始化为一个很大的数比如9999999那整个更新逻辑就废了这个属于低级失误。并列情况更需要注意。题目要求输出获得最多奖学金的学生如果多个学生金额相同应该取最先输入的那个。我代码里用的是if (money maxMoney)注意这里一定是“大于”不是“大于等于”。如果写成了“大于等于”那么当后面出现一个同等金额的学生时会覆盖掉之前记录的姓名最终输出的可能就不是最先出现的那个人与题意不符。其实这种“取第一个最大值”的写法也是很多实际业务场景中的通用规则。比如从日志里找最早达到某个阈值的记录用大于号就能保证永远不会被后来的同值记录覆盖。4.4 总额变量的取值范围N的数据范围在题面上给的并不算大一般不超过100。每个学生最高能拿的奖学金是8000加4000加2000加1000加850等于15850元。100个人的总额上限也就1585000左右int类型完全足够。但如果你是从其他OJ上找到的改编版本N有可能被放大或者奖学金的单项金额被调整这时用int可能就不够稳了。保险起见可以把总额声明成long long养成习惯既不会多花你一秒也能避免极端数据溢出。我在实际教学里见过有人因为总额变量用了int在自定义数据上爆掉的情况。虽然这不是原题的数据范围问题但它提醒我们一个通用原则凡是涉及累加和的数据先想清楚最坏情况有多大再决定类型不要想当然。5. 延伸如果题目变了代码怎么改5.1 推广到“通用规则表”这道题看起来固定了五个条件但实际生产中你可能会遇到类似的问题用户符合哪些条件就能获得对应奖励奖励金额不同条件数量还可能动态变化。这种时候把五个if直接写死就很吃力。一个更灵活的做法是抽出一个规则表每条规则包含“触发条件”和“奖励金额”然后用循环统一判断。比如struct BonusRule { int amount; bool (*check)(int avg, int cls, int papers, bool leader, bool west); };如果你愿意完全可以定义五个函数分别表示五条规则然后放进数组里循环执行。这样新增一条规则时不需要修改主循环逻辑只要在规则数组里加一项。这种设计模式在真实的企业级开发里非常常见也就是“策略模式”的简化版。当然对这道题来说五个if更直观也更不容易出bug。写出可扩展的代码不是目的目的是让你意识到简单的题目里也可以埋下设计的种子。5.2 大数据量场景下的处理方式如果N从100变成1000万思路有没有变化其实没有。边读边算本来就是O(N)复杂度额外空间O(1)不管N多大这个方案都能稳定运行。但如果这时候你还坚持存结构体数组然后排序那内存消耗就成了问题。假设一个学生结构体占50字节左右1000万条数据就是500MB普通OJ根本不可能让你跑过。所以我在前面强调读入即处理不仅是代码量更少的问题它天然具备处理大规模数据的能力。很多初学者意识不到这种思路的价值直到做海量日志处理或者流式计算项目时才后悔当年没把这种思维刻进脑子里。5.3 从竞赛题到业务场景的类比如果把“谁拿了最多奖学金”映射到现实业务就是一个典型的“多条件权益计算”场景。比如电商平台给用户发优惠券注册满一年且消费金额超过5000发100元券。VIP用户且近30天有登录发50元券。新用户首次下单发30元券。每个用户符合哪些条件就累加哪些券。运营需要知道谁获得的总券额最高同时也要统计本轮活动发放的总券额。这和奖学金题的结构一模一样。从这个角度看这道经典题给的价值并不只是在竞赛里拿分。它教给你的“逐条判断、立即累加、持续维护最大值”这套流程在很多真实的数据统计场景里都有一模一样的应用。这也是为什么很多高校OJ和培训机构都愿意把它放在入门题单第一道题的原因之一。6. 最后的实操建议我在指导别人做这道题时总习惯让他们先别急着写代码拿出一张草稿纸把五个条件用表格画出来条件列、金额列、判断方向列都写清楚。做完这一步再动手写起代码来会顺畅很多也几乎不可能漏掉条件。如果你已经写完了代码并提交建议自己再多构造几组边界数据测试不要只依赖样例。比如全部条件都不满足的学生看他贡献的money是不是0。平均成绩恰好80、85、90的学生确认没有拿到对应的奖学金。论文数为0和论文数为1的对照。两个学生奖学金相同确认输出的是先出现的那一个。这种“自造测试数据”的习惯比反复提交评测去碰运气要有效得多。我个人早期的教训是有一次把“是否西部学生”写成了先读char再比较字符串结果读到一个换行符整个判断全部错位样例都过不了。后来我统一改成string读入问题立刻消失。从那以后但凡题目里出现Y/N这种标记我都不用char去处理。这道题虽然简单但把它的每一个细节吃透比草草写对一次提交更值得。条件如何拆解、数据如何流式处理、边界如何校准、并列如何取舍这些思维方式的打磨才是做竞赛题真正沉淀下来的东西。