如果你刷过 PAT 真题大概率会在“1085 PAT单位排行”这道 25 分题上卡几下。它第一眼看起来就是普通排序读一堆考生信息按学校聚合算总分输出排名。但真正动手你会发现它把“字符串归一化、浮点精度、多条件排序、并列名次跳跃”四个坑全塞进了一道题里任何一个没处理干净就是 WA。这篇文章就把从读题到 AC 的完整思路拆开讲代码和踩坑点都直接给出适合刚开始刷甲级/乙级排序题、或者对这类“榜单题”总拿不准的同学。这道题的核心需求不复杂给 N 个考生的准考证号、得分和学校统计每个学校的加权总分和考生人数然后按“总分、人数、学校名”三个关键字排出榜单。但正因为需求说得太直白反而容易让人忽略细节。下面从数据读入、分数计算、排序逻辑、常见错误四个层面完整过一遍最后附 C 和 Python 两版可直接提交的代码。1. 题目到底在问什么把真实需求拆成三个小问题1.1 输入数据三个字段分别扮演什么角色每行输入包含三个信息准考证号、得分、学校。准考证号的首字母决定考生的级别进而决定分数权重这是整道题最容易看错的地方。级别分为三种B 对应乙级A 对应甲级T 对应顶级加权规则是乙级和顶级得分乘 1.5甲级得分乘 1。也就是说一个考 50 分的乙级考生实际贡献给学校的分数是 75一个考 50 分的甲级考生贡献只有 50。学校名由不超过 6 个英文字母组成题目说“大小写不敏感”所以输入给你的可能是混合大小写输出榜单时统一用小写。很多人在这一步就不做任何字符串处理直接把输入原样输出后面字典序排序自然全错。正确做法是每读到一条学校名先把它转成小写后续所有聚合、比较、输出都基于小写形式。这里的“先规范化再处理”是一个通用意识以后做任何涉及字符串去重、聚合的题都用得上。得分是 [0,100] 区间内的整数读入时可以直接用 int 存。人数统计也不需要额外判断每个考生一行学校每次出现就把人数加 1。1.2 榜单排序的三个关键字顺序输出时先在第一行打印学校总数然后从第二行开始输出榜单。榜单排序规则非常明确第一关键字是学校加权总分从高到低第二关键字是学校人数从低到高第三关键字是学校名的小写字母序从 a 到 z。这里有个很容易读反的细节第二关键字是“人数少的排前面”不是人多的排前面。题目这么设计其实很好理解总分相同的学校人数更少意味着平均分更高排在前面更合理。如果你凭直觉写成人数多的排前面样例大概率直接挂掉。多关键字排序在算法题里非常常见关键在于弄清楚每个关键字是升序还是降序以及谁优先。建议把关键字顺序写在草稿纸上再动手写比较函数。1.3 并列名次是跳跃占位不是顺序编号第三个容易被忽略的规则是并列名次。如果两个学校总分相同它们名次相同下一个不同总分的学校名次不是“上一个名次 1”而是“当前输出序号 1”。举个例子第一个学校总分 100 名次是 1接下来两个学校总分都是 90名次都是 2第四个学校总分 80名次直接跳到 4。这个规则和查成绩时的体验一致你和同桌总分相同你俩都是第 2 名下一个同学虽然是第三个人但名次是第 4 名因为前面有两个人占住了第 2 名的位置。实现上这是整个题最容易出错的地方很多人写成名次每次都自增 1输出变成 1 2 2 3边界测试就会暴露问题。后面第 3 章专门讲这个跳跃怎么用代码实现。2. 数据读入与预处理分数计算里的精度陷阱2.1 权重表与乘 2 技巧加权规则如果不仔细想直接写一句sum score * 1.5也能跑但这里藏着一个精度隐患。1.5 在计算机二进制里不是精确表示的多次累加之后本应相等的两个总分可能因为浮点误差被判断成不相等进而导致名次错误。虽然是 25 分题但这种隐蔽的浮点问题恰恰是很多人 WA 到怀疑人生的原因。稳妥做法是全体分数乘以 2让所有累加项都变成整数首字母级别原始权重乘 2 后的单次累加值A甲级1.0score * 2B乙级1.5score * 3T顶级1.5score * 3这样整个程序全程没有任何浮点运算。最终统计出来的“总分 × 2”在输出前再除以 2 取整正好对应题目要求的“加权总分取整数部分”。为什么乘 2 而不是乘 10因为 1.5 乘以 2 得到一个整数 3累加值最小、运算最快int 范围完全够用。N 最大在 10 万级别每个考生最高 100 分最多累加到 3 × 10^7 左右远没到 int 上限。顺便说一个通用经验以后遇到带 0.5 权重的题优先考虑同倍放大成整数再聚合不要硬扛浮点。这个技巧在不少涉及到“分数加权后取整”的题里都能省很多事。2.2 学校名归一化统一小写再干活因为题目要求按学校名小写字母序排序而且输入可能是大小写混合读入后必须第一时间把学校名转成小写。C 里最直接的方式是遍历字符串的每个字符调用tolowerfor (char c : school) { c tolower(c); }注意tolower函数返回的是 int直接赋值给 char 没有问题。如果你用的是 Python一行school school.lower()就能解决语言层面的便利性确实不一样。这个“先归一化再比较”的细节本质上和很多 SQL 查询里的LOWER(column)思路一致。字符串大小写不一致的问题在排行榜、分组统计、去重场景里极易出现养成读入即转换的习惯比后面在排序比较函数里反复处理要省心得多。2.3 用两个 map 完成学校聚合聚合逻辑可以拆成两个 map一个存加权总分乘 2 后的整数一个存人数。C 里直接用mapstring, intmapstring, int mpScore; // 加权总分 * 2 mapstring, int mpCnt; // 人数每读一行先转小写再根据首字母决定累加值然后mpScore[school] add; mpCnt[school] 1;用map的好处是第一次访问一个还没出现过的学校时会自动创建并初始化为 0然后直接累加不需要提前判断 key 是否存在。虽然unordered_map理论更快但 N 在 10 万规模下map的 O(log M) 完全够用而且map遍历时按 key 有序后面构造输出列表时至少不会乱。这个选择不是性能瓶颈怎么顺手怎么来。一个容易犯的错误是“覆盖赋值”比如有人会在读入时用mpScore[school] add导致后读的考生把前面该学校累加的分数覆盖掉。只有用才是累加用就是覆盖这类 25 分题里出现这种低级错误确实不值得。3. 排序逻辑怎么写才不出错从 map 到 vector 再到输出3.1 为什么要倒进 vector 再用结构体map的默认排序是按键学校名字典序但题目要求的排序是“总分降序、人数升序、名字升序”和map自带排序不一致。所以数据聚合完成后必须把数据搬到可以自由定制排序规则的容器里。定义一个结构体存最终榜单需要的三列信息struct School { int score; // 最终整数总分 int cnt; // 人数 string name; // 小写学校名 };然后遍历mpScore组装成vectorSchoolvectorSchool schools; for (auto p : mpScore) { schools.push_back({p.second / 2, mpCnt[p.first], p.first}); }这里p.second / 2是整数除法直接舍弃小数部分正好等价于“取整数部分”。有人可能会疑惑为什么这里就要除以 2而不是排序之后再除因为排序依据必须是最终展示给评测系统的那个整数总分。如果拿乘 2 后的 3 和 2 去比较相当于两个学校实际整数总分都是 1却被分成了不同名次这道题就彻底错了。3.2 三关键字比较函数怎么写sort函数需要传入一个比较规则。C 里我习惯直接用 lambda简短清晰sort(schools.begin(), schools.end(), [](const School a, const School b) { if (a.score ! b.score) return a.score b.score; if (a.cnt ! b.cnt) return a.cnt b.cnt; return a.name b.name; });三个条件按顺序判断先比总分总分不同就直接返回总分大的在前总分相同再比人数人数少的在前人数也相同最后比名字字母序小的在前。这里所有条件都写全了没有条件写全的排序也最容易出现“样例过了但没考虑的边界”之类问题。比如只有总分和人数都相同但你的比较函数忘了比较名字sort的行为是未定义的结果不稳定测试点就可能随机出错。3.3 并列排名的跳跃实现排名不是排序函数的一部分而是在输出阶段根据“上一个学校的总分”动态生成。经典写法是int rank 1; for (int i 0; i (int)schools.size(); i) { if (i 0 || schools[i].score ! schools[i - 1].score) { rank i 1; } cout rank schools[i].name schools[i].score schools[i].cnt \n; }核心逻辑就一句话总分和上一个不同说明进入新的一组名次更新为i 1总分和上一个相同名次沿用之前的值不再自增。因为i是当前元素在序列中的索引i 1天然就能表示“跳过了并列占位之后的名次”。把 100、90、90、80 四个分数代进去走一遍第一个输出 1第二个输出 2第三个因为和上一个总分相同保持 2第四个从 3 号位置开始但名次更新为 4。这个思路看起来简单实际写题时很多人会用一个rank的变量递增最后得到 1 2 3 4这种错误不自己造边界数据很难发现。还需要注意输出格式榜单开始前要先输出学校总数也就是schools.size()。然后每一行是“排名 学校 总分 人数”中间用空格隔开行尾不要有多余空格。PAT 对输出格式判定比较严格尽量让输出和样例格式完全一致。这里我习惯把“排名、学校、总分、人数”这四列的变量名用rank、name、score、cnt和结构体字段一一对应在写输出语句时不容易写串列。4. 难点分析与常见错误排查这些坑我几乎每次讲都会提4.1 double 精度隐藏坏账怎么彻底避开如果用 double 直接累加有一个很隐蔽的问题分数在计算机里以二进制近似存储两个学校本应完全相等的总分可能因为浮点误差被判成不同。举个例子学校甲有两次乙级 50 分贡献是 50 × 1.5 × 2 150double 累加出来看起来是 150但另一个学校通过别的方式累加出 150两个 150 用比较时却不一定相等。输出时被整数化掩盖了但排序时直接用 double 比较误差就会影响名次。最稳妥的方案就是第 2 章说的乘 2 技巧。全程 int 累加排序比较的是已经整除过的整数总分所有相等判断都是精确的从根上消灭精度问题。这个技巧值得多体会几次以后凡是遇到“权重带 0.5 且最后取整”的题目第一反应都应该是能不能放大成整数4.2 并列排名占位问题怎么自测检验排名逻辑对不对最快的方法是自己构造一组全是并列的数据。比如三所学校总分都是 90那么前三行输出名次应该是 1、1、1第四个学校总分哪怕只低 1 分名次也必须是 4不是 2 也不是 3。如果你实现的还是rank那种递增方式第四个学校名次会变成 2这个错误在样例里可能完全看不出来因为样例的分差往往不产生密集并列。自己造数据是刷题非常关键的能力尤其是这类边界极值题别依赖样例帮你兜底。4.3 排序依据是整数总分不是内部精确分这一点是乘 2 方案最容易踩的隐藏坑。加权总分乘 2 之后是 3 和 2但最终输出是 1 和 1。排序时必须拿“最终展示的整数总分”比较也就是除以 2 之后的值如果拿 3 和 2 直接排就会把两个输出名次应该并列的学校拆成先后两名。为什么会有人犯这个错因为一开始觉得“反正所有学校都乘 2相对大小不变”。但问题是题目要求取整后再排取整这个操作会改变相对大小关系。1.5 和 1.0 在乘 2 后是 3 和 2相对大小不同取整后都是 1名次却要相同。所以不管怎么放大最终比较的底数必须是“输出时那个整数”。4.4 容易被忽略的输出细节学校个数、大小写、行尾空格输出榜单纯粹每行打印也不够题目要求第一行先打印学校总数。很多人聚合、排序、排名都写对了就是把这一行漏了直接扣分。学校个数其实就是schools.size()在循环输出前打印一次即可。学校名大小写问题前面已经强调过。注意读入时必须转小写输出也自然就是小写不需要在输出时再做一次转换。行尾格式方面PAT 通常不强制要求无行尾空格但规范一点总是好的输出时用空格连接各列别在末尾手动追加空格。还有一个小细节如果学校加权总分为 0也要参与输出因为题目没有说过滤掉 0 分学校。只要这个学校有考生就要出现在榜单里。有人会习惯性加一个if (score 0)的判断这就错了。5. 完整参考代码C / Python5.1 C 可直接提交版本#include bits/stdc.h using namespace std; struct School { int score; // 最终整数总分 int cnt; // 考生人数 string name; // 小写学校名 }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; mapstring, int mpScore; // 加权总分 * 2 mapstring, int mpCnt; // 人数 string examId, school; int score; for (int i 0; i n; i) { cin examId score school; for (char c : school) { c tolower(c); } if (examId[0] A) { mpScore[school] score * 2; // 甲级权重 1 } else { mpScore[school] score * 3; // 乙级、顶级权重 1.5 } mpCnt[school]; } vectorSchool schools; for (auto p : mpScore) { schools.push_back({p.second / 2, mpCnt[p.first], p.first}); } sort(schools.begin(), schools.end(), [](const School a, const School b) { if (a.score ! b.score) return a.score b.score; if (a.cnt ! b.cnt) return a.cnt b.cnt; return a.name b.name; }); cout schools.size() \n; int rank 1; for (int i 0; i (int)schools.size(); i) { if (i 0 || schools[i].score ! schools[i - 1].score) { rank i 1; } cout rank schools[i].name schools[i].score schools[i].cnt \n; } return 0; }代码里我把输入和输出流同步关掉了避免数据量大时 cin/cout 拖慢速度。虽然这题 N 不大但养成好的 IO 习惯没有坏处。examId[0]的判断只分 A 和非 A因为 B 和 T 权重相同可以直接归到 else 分支如果你觉得这样可读性差也可以写成examId[0] B || examId[0] T分别处理效果一样。5.2 Python 参考思路与代码Python 刷题时思路和 C 完全一致用两个字典做聚合最后组装成元组列表排序。一个很方便的技巧是元组默认按第一、第二、第三个元素升序排列所以把总分取负数存进去这样总分大的自然排前面而人数和学校名仍然按升序排正好满足题目要求。import sys from collections import defaultdict def main(): input_data sys.stdin.read().split() n int(input_data[0]) idx 1 mp_score defaultdict(int) mp_cnt defaultdict(int) for _ in range(n): exam_id input_data[idx] score int(input_data[idx 1]) school input_data[idx 2].lower() idx 3 if exam_id[0] A: mp_score[school] score * 2 else: mp_score[school] score * 3 mp_cnt[school] 1 items [] for name in mp_score: final_score mp_score[name] // 2 items.append((-final_score, mp_cnt[name], name)) items.sort() rank 1 out_lines [str(len(items))] for i, (neg_score, cnt, name) in enumerate(items): score -neg_score if i 0 or score ! -items[i - 1][0]: rank i 1 out_lines.append(f{rank} {name} {score} {cnt}) sys.stdout.write(\n.join(out_lines)) if __name__ __main__: main()Python 里//是整数除法对正数直接截断小数位正好对应取整。如果你平时用sorted时喜欢加keylambda x: (-x[0], x[1], x[2])也可以不用负号技巧两种方案都行。我习惯用负号是因为当元组本身已经包含所有排序依据时直接排序更简练。6. 实战建议从这道题能带走的“榜单题”通用套路6.1 一套四步走的聚合排序模板这类题做多了会发现一个固定套路读入阶段完成聚合输出前把聚合结构转成可排序的数组再写一个三关键字排序最后输出时用i 1处理并列名次。把这四步固化下来遇到很多“排行榜”“单位统计”“部门绩效”之类的题目都能直接套。聚合阶段的核心是搞清楚按哪个字段分组、要累加哪些值排序阶段的核心是分清升降序和优先级输出阶段的核心是并列名次和多余格式。这道题的难点恰好分布在每个阶段各一个所以很适合当作模板题反复刷。6.2 拿到题先做三件事再动手第一把加权规则、排序关键字、取整方式写在草稿纸上特别是“要不要取整”和“人数是升序还是降序”第二自己造一组包含并列总分、不同人数、不同名字顺序的数据手推一遍期望输出第三再开始写代码。很多人觉得刷题浪费时间其实最耗时间的不是敲代码而是没想清楚规则就动手然后反复提交试错。6.3 精度策略能上整数就不要碰浮点我现在遇到带小数权重的题第一反应永远是“能不能通分放大成整数”。乘 2、乘 10、乘 100只要放大后不超 int 范围就优先用整数。浮点方案虽然代码看起来更短但排查成本很高考试环境下不值得冒险。类似地涉及“向下取整”“截断小数”的题也要确认取整函数用的是不是正确的那一种C 里 int 除法对正数直接截断Python 里用//这两个才是常见做法。最后分享一个小技巧凡是排名题先问自己三个问题——排序依据是哪个数并列怎么跳输出要不要取整把这三个问题的答案写在注释里再写代码基本就不会翻车。这道题我后来每次讲排序都会拿出来因为它把榜单题里最喜欢埋的坑全部集中在了一个 25 分小题里。认真刷完它再遇到各种排行榜、聚合统计、复杂排序的题目你都会比原来有底气很多。