PAT甲级的题刷到1036这道Boys vs Girls时很多人第一反应是不就是找个最高分女生和最低分男生吗有什么好讲的我当初也这么想结果连续提交了几次才AC问题全藏在边界条件和输出顺序里。这道题的代码量很小但它把“读题时漏掉一个细节评测就给你颜色看”这件事体现得淋漓尽致。如果你是刚开始刷PAT、准备考研机试或者想系统补一补算法题里的极值维护套路这篇拆解应该能帮你少走几次弯路。我会把题目规则、解题思路、C与Python的双版本实现以及我实际踩过的坑完整过一遍。1. 题目到底在考什么规则细节决定了你会不会WA1.1 完整题意与输入输出形式题目会先给一个正整数N表示学生总数接下来N行每行给出一个学生的姓名、性别、学号和成绩四个字段用空格分隔。姓名和学号都是不超过10个字符的字符串性别是单个字符F或M成绩是0到100的整数。要求的输出是三行女生中成绩最高的那位输出其姓名和学号男生中成绩最低的那位输出其姓名和学号如果上述两个人都存在输出“最高女生成绩 - 最低男生成绩”的整数差值如果任一缺失则输出NA。如果某一性别没有任何学生对应位置输出Absent。这里我建议大家不要急着写代码先把输出顺序和判定规则刻在脑子里。我见过不少人把第三行的差值算对了却因为第一行该输出Absent的位置输出成了别的整题直接零分。顺序错了就是WA这个词在OJ里听起来极其刺耳。1.2 四种情况用表格列清楚为了让逻辑更直观我整理了一个四类情况的对照表。假设女生最高成绩变量是girlScore男生最低成绩变量是boyScore初始状态分别是-1和101那么判定结果如下情况第一行第二行第三行有女生且分数增量更新过也有男生且分数减量更新过女生姓名 学号男生姓名 学号girlScore - boyScore只有女生没有男生女生姓名 学号AbsentNA只有男生没有女生Absent男生姓名 学号NA两者都没有AbsentAbsentNA虽然题目保证N至少为1所以“两者都没有”理论上不会出现但代码里也不怕多写一个分支逻辑完备性永远没坏处。1.3 一个完整样例的手推过程我自己刷题有个习惯无论题目多简单先把样例手推一遍确认自己真的懂了。比如这样一个输入5 Amy F 1001 90 Bob M 1002 88 Cathy F 1003 95 David M 1004 70 Eve F 1005 86第一轮Amy是女生成绩90记录当前最高分女生为Amy 第二轮Bob是男生成绩88记录当前最低分男生为Bob 第三轮Cathy是女生成绩95比90高更新最高分女生为Cathy 第四轮David是男生成绩70比88低更新最低分男生为David 第五轮Eve是女生成绩86没有超过95不更新。最终输出Cathy 1003 David 1004 25第三行的25就是95减70。这个手推过程看起来简单但它能帮你提前确认代码里比较符号、更新条件、输出变量名的对应关系避免写代码时搞反。2. 解法思路为什么一次扫描就够了排序属于想多了2.1 从问题本质出发先想清楚“要找什么”这道题的本质是找两个极值女生群体中的最大值男生群体中的最小值。找极值这件事天然适合线性扫描。你只需要让数据流经眼前一次在每个时刻记下当前见过的人里的最优结果扫描结束答案也就出来了。那为什么很多人第一反应是排序因为“最高”和“最低”这类词容易让人联想到有序序列。把所有人按成绩排个序然后挑出女生里成绩最高的和男生里成绩最低的确实可行。但排序的复杂度是O(N log N)而这里我们只需要两个极值排序会把大量根本用不上的中间过程也算一遍属于典型的杀鸡用牛刀。更重要的一点是排序还引入了额外的麻烦如果按成绩升序排你要找女生里最后一个F按降序排你要找男生里最后一个M。排序规则、性别过滤、边界索引都要考虑代码量一点也不比线性扫描少反而更容易写错。2.2 哨兵值的选择与理由线性扫描的核心是初始化极值变量这地方最讲究。因为女生要找最高分初始值必须是一个比任何合法成绩都小的数男生要找最低分初始值必须是一个比任何合法成绩都大的数。成绩合法范围是0到100所以girlScore初始为-1只要遇到女生score 0一定大于-1必然能触发更新boyScore初始为101只要遇到男生score 100一定小于101必然能触发更新。这样做的另一个好处是扫描结束之后如果girlScore仍然是-1说明一个女生都没有出现过如果boyScore仍然是101说明一个男生都没有出现过。这个哨兵值同时承担了“是否存在学生”的判断职责你不用额外维护一个布尔变量或计数器。2.3 比较符号用严格大于和严格小于别随便用大于等于这道题明确说明最高分女生和最低分男生都是唯一的所以用还是一直用最终结果都一样。但我的建议是代码里写严格大于和严格小于原因有两个第一更贴合“最高”“最低”的语义。最高分意味着“比所有其他人都高”用严格大于更自然 第二万一以后遇到数据不保证唯一的情况你可以根据题意决定是保留最先出现的人还是最后出现的人。用严格大于会保留最先出现的人用大于等于会保留最后出现的人这个细节在别的题目里可能是区分点。3. 代码实现细节C和Python双版本附坑点注释3.1 C版用scanf/printf保持清爽先写C版本因为PAT甲级用C提交的比例最高运行速度也稳定。#include cstdio #include cstring int main() { int n; scanf(%d, n); char name[15], id[15], gender; int score; char girlName[15] , girlId[15] ; char boyName[15] , boyId[15] ; int girlScore -1; int boyScore 101; for (int i 0; i n; i) { scanf(%s %c %s %d, name, gender, id, score); if (gender F score girlScore) { girlScore score; strcpy(girlName, name); strcpy(girlId, id); } else if (gender M score boyScore) { boyScore score; strcpy(boyName, name); strcpy(boyId, id); } } if (girlScore -1) { printf(Absent\n); } else { printf(%s %s\n, girlName, girlId); } if (boyScore 101) { printf(Absent\n); } else { printf(%s %s\n, boyName, boyId); } if (girlScore -1 || boyScore 101) { printf(NA\n); } else { printf(%d\n, girlScore - boyScore); } return 0; }这段代码里我用的是C风格字符串和strcpy因为题目给的姓名、学号长度不超过10直接开char[15]就够了。如果你更习惯C的std::string完全没问题只是注意用cin的时候加上ios::sync_with_stdio(false)不然某些评测环境上的大数据输入会慢得让你怀疑人生。3.2 Python版简洁可读注意读入方式n int(input()) girl_name girl_id boy_name boy_id girl_score -1 boy_score 101 for _ in range(n): name, gender, sid, score_str input().split() score int(score_str) if gender F and score girl_score: girl_score score girl_name name girl_id sid elif gender M and score boy_score: boy_score score boy_name name boy_id sid if girl_score -1: print(Absent) else: print(girl_name girl_id) if boy_score 101: print(Absent) else: print(boy_name boy_id) if girl_score -1 or boy_score 101: print(NA) else: print(girl_score - boy_score)Python版本的核心逻辑和C完全一致。唯一要注意的是如果N非常大比如10万行输入用input()逐行读可能偏慢可以改成一次性读取后按空格切分。不过这道题的N范围决定常规input()完全够用我写这段代码时特意没加sys.stdin.buffer是为了让新手把注意力集中在题目本身的逻辑上不要被IO优化分散精力。3.3 评测环境里那些容易被忽视的运行时细节如果你用C提交这几个点我建议形成肌肉记忆如果用cin记得在main开头加ios::sync_with_stdio(false); cin.tie(0);否则大数据量下C的IO同步会让你吃亏数组长度至少开到字符串最长长度加1因为C风格字符串末尾有\0读单个字符时注意scanf(%c)会读入空格和换行所以这里用scanf(%s %c %s %d, ...)是最省心的空格和换行天然被跳过。如果你用Python提交我建议不要在一行里写太多split嵌套宁可多写几步也要保证变量名能对上逻辑。OJ刷题不是为了秀语法而是为了稳定地拿分。4. 踩坑记录三次WA之后我才搞明白的边界问题4.1 第一次WA男生最低分初始化为0思路直接崩了我一开始写男生最低分时下意识用了0理由是“成绩最低也就是0了”。结果循环里遇到第一个男生成绩88score boyScore变成88 0不成立boyScore永远停留在0。等到输出时最低分男生的姓名学号全部是空字符串因为更新条件从来没触发过。这个问题其实非常容易犯尤其是成绩范围在0到100时大脑会默认0就是最小值。但你要找的是“当前见过的最低分”初始值必须设为比你见过的所有合法成绩都大的数这样才能保证第一个男生出现时必定触发更新。我后来养成了习惯找最小值就初始化成“上界加一”找最大值就初始化成“下界减一”。这道题里上界是100所以101就是最自然的哨兵。4.2 第二次WA第三行的NA判断写成了基于字符串第二版代码我改对了初始化但第三行判断写成了if (girlName || boyName )。在Python里这样写还能直接用但在C里两个char数组不能直接用比较内容我写成了if (girlName || boyName )编译不通过改来改去又引入了一堆strcmp。后来我意识到与其比较字符串不如直接看哨兵值。girlScore是不是还是-1boyScore是不是还是101这两个判断在代码里更短、更不容易出错而且字符串变量和成绩变量是同步更新的判断成绩变量的值就等于判断学生是否存在。从那之后我的习惯变成了凡是需要标记“是否出现过”的数据优先用与数据本身同一个变量初始化的哨兵值而不是单独维护字符串状态。4.3 第三次WA输出顺序在微调代码时被搞反前两个问题解决后我又犯了一个非常低级的错误。因为觉得逻辑已经稳了就顺手把第三行差值提前输出到前面想着“反正最后都要输出顺序不重要”。结果提交上去直接WA几乎零分。评测机对输出内容的顺序和格式敏感得吓人你多一个空格、少一个换行、顺序反一行结果都是不匹配。正确的顺序永远是先判断最高分女生是否存在输出她的姓名学号或Absent再判断最低分男生是否存在输出他的姓名学号或Absent最后根据前两个判定结果决定输出差值还是NA。这个顺序不是算法上的强制要求而是评测规范的要求。题目的输出格式就是你的协议协议怎么定你就怎么执行千万不要“优化”掉任何看起来多余的东西。4.4 如何自己构造边界用例把Bug提前炸出来如果你也经常被边界用例坑我给你一套非常实用的自测方法写完代码后不要光盯着样例必须构造下面三类边缘输入。第一类只有一个女生1 Amy F 1001 90期望输出Amy 1001 Absent NA第二类只有一个男生1 Bob M 1002 80期望输出Absent Bob 1002 NA第三类成绩全为0或全为100的极端情况2 Amy F 1001 0 Bobb M 1002 100期望输出Amy 1001 Bobb 1002 -100注意最后这个例子里差值是负数这说明你输出的第三行用%d是能应付负数的Python的print也没问题。把这三组用例在本地跑一遍再提交到OJ基本就不会出现因为边界条件导致的WA。5. 从1036延伸出去极值维护套路与刷题节奏5.1 同套路题目对比1006、1028与1036的共性单独刷一道1036意义有限我更推荐把它和几道同套路的题放在一起刷比如PAT甲级1006 Sign In and Sign Out它要找出最早到的人和最晚离开的人思路和1036完全一致维护两个极值分别附带对应的人名信息。还有1028 List Sorting那道题本质是排序但你可以体会一下“需要有序结果”和“只需要极值结果”在算法选择上的本质区别。做一个简单的对比表题号要找的目标核心策略与1036的异同1036女生最高分、男生最低分单次扫描维护两个极值本体1006最早到达、最晚离开单次扫描比较时间字符串极值从整数变成字符串1028按指定字段排序排序重点是编写比较规则极值退化为排序后的首尾这三道题合在一起看你能发现一个特别明显的规律凡是只需要“一个最大”或“一个最小”的题优先想单次扫描凡是需要“整体有序”或“某个名次段”的题才需要排序。这个判断逻辑比死记硬背算法模板有用得多。5.2 写题前的三个自问我刷题刷到中途总结出了三个下笔前必须问自己的问题每次都能帮我减少Reactive改代码的时间它要的是极值还是有序序列决定用扫描还是排序极值的初始值设多少找最大就设成小于下界找最小就设成大于上界如果有多个输出分支那些分支的顺序是什么先在草稿纸上把四类情况列出来再开始写。这三个问题想明白了像1036这种题基本是十分钟内解决战斗。如果上来就敲代码大概率要经历我那种“连续提交三次”的尴尬。5.3 我的建议把每一道简单题都当成边界训练最后说点题外话。现在很多人刷题喜欢挑难题觉得简单题没营养。但根据我自己的经验真正决定机试能不能稳过的往往是简单题的正确率。1036这样的题算法难度几乎为零可一旦边界处理不到位照样会WA。你在这个题上花十分钟把边界想清楚比硬啃一道难题更能提升赛场稳定性。我后来给自己定了个小目标简单题全部一遍AC不接受任何“反正思路对改一改就能过”的侥幸心态。这个习惯帮我省下了大量重交和调试的时间也让我在真正比赛时心态会稳定很多。所谓“稳”不是某种玄学而是把能控制的每一个细节都控制住。如果你正好在准备PAT或者类似的机试我真心建议你把1036这道题当作一面镜子题目越简单越能照出你的读题习惯和代码规范。把这些细节认真对待起来比你多做十道难题都划算。