★ FEATURED ARTICLE 1. 从一道25分题说起排名汇总到底在考什么PAT排名汇总这道题我第一次做的时候也踩了不少坑。题目本身不复杂但涉及到的细节特别多稍不注意就会在某些测试点上翻车。这道题的核心场景是这样的有多个考场每个考场有若干考生每个考生有考号和成绩。你需要输出所有考生的总排名同时还要输出他们在各自考场内的排名。听起来很简单对吧但问题在于排名规则和并列处理这两个点是很多人丢分的地方。再加上数据量可能不小排序的效率也得考虑。所以这道题虽然只有25分但它考察的东西挺全面的结构体排序、多关键字排序、并列名次的处理、以及跨考场数据的合并。我后来把这道题反复做了几遍每次都有新的体会。今天就把我对这道题的理解完整地分享出来包括思路拆解、代码实现、以及我在实际编码中踩过的那些坑。如果你正在准备PAT考试或者想巩固排序相关的知识这篇内容应该能帮到你。这道题适合哪些人看呢如果你已经掌握了C的基本语法知道结构体是什么用过sort函数那就可以直接上手。如果你对sort的第三个参数还不太熟悉也没关系我会在文中详细解释自定义比较函数的写法包括为什么要那样写。2. 题目核心需求拆解与整体设计思路2.1 输入输出格式的精确理解先把题目的输入输出要求理清楚。输入的第一行是一个正整数N表示考场的数量。接下来是N个考场的数据每个考场的第一行是该考场的考生人数K然后是K行每行包含考生的考号和成绩。输出要求是这样的第一行输出总考生人数。然后按照总排名从高到低输出所有考生的信息每行包括考号、总排名、考场号、考场内排名。如果总成绩相同则排名并列但输出顺序需要按照考号从小到大排列。这里有个容易忽略的点并列排名的处理。比如两个人都是100分那他们的总排名都是1下一个人是99分那他的排名就是3而不是2。这个规则在PAT里很常见但每次都要小心。还有一个细节输出的时候考场内排名也要按照同样的规则处理。也就是说同一个考场内如果两个人分数相同他们的考场内排名也是并列的。2.2 数据结构的选择与理由这道题最核心的数据结构就是一个结构体用来存储每个考生的信息。我一般会这样定义struct Student { string id; // 考号 int score; // 成绩 int location; // 考场号 int rank_all; // 总排名 int rank_local; // 考场内排名 };为什么用string存考号因为考号可能包含前导零用整数存会丢失这些零。虽然题目里考号是13位的数字但用string更保险也方便输出。为什么需要location字段因为输出的时候要标明每个考生属于哪个考场。考场号从1开始编号这个在输入的时候就能确定。rank_all和rank_local这两个字段是后面计算出来的初始时可以不管。2.3 整体流程设计整个题目的处理流程可以分成这么几步读取所有考场的数据把每个考生的信息存入一个大的vector中同时记录每个考生的考场号。对所有考生按照总成绩从高到低排序。如果成绩相同按照考号从小到大排序。遍历排序后的数组计算每个考生的总排名。注意处理并列的情况。对每个考场内的考生按照同样的规则排序计算考场内排名。按照总排名的顺序输出所有考生的信息。这里有个关键点总排名的输出顺序。题目要求按照总排名从高到低输出如果总排名相同则按照考号从小到大输出。所以我们在排序的时候就要把这两个条件都考虑进去。2.4 为什么选择这样的方案有人可能会想能不能不存储所有考生而是边读边处理理论上可以但实际操作起来会很麻烦。因为总排名需要全局排序考场内排名需要分组排序如果边读边处理就得反复扫描数据效率反而更低。把所有数据读进来然后统一排序这是最直观也最高效的做法。数据量方面PAT的题目一般不会超过10^5个考生用vector存储完全没问题。sort的时间复杂度是O(n log n)对于10^5的数据量来说完全可以在1秒内跑完。另外关于并列排名的计算我选择在排序之后遍历一遍数组来计算。这样比在排序过程中计算要简单得多也不容易出错。3. 核心细节解析与实操要点3.1 自定义比较函数的写法与原理sort函数是C标准库里的排序算法默认是从小到大排序。但我们需要按照成绩从高到低排序所以必须自定义比较函数。比较函数的写法是这样的bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; // 成绩高的排前面 return a.id b.id; // 成绩相同考号小的排前面 }这个函数的意思是如果a的成绩不等于b的成绩那么成绩高的排在前面如果成绩相同那么考号小的排在前面。这里有几个细节需要注意第一参数要用const引用。这样避免拷贝提高效率。虽然对于结构体来说拷贝的开销不算大但养成这个习惯是好的。第二比较函数必须是严格弱序。什么意思呢就是说对于任意两个元素a和bcmp(a, b)和cmp(b, a)不能同时为true。如果同时为truesort函数的行为就是未定义的可能会导致程序崩溃。第三不要用或。在比较函数里应该用或而不是或。因为如果用了当两个元素相等时cmp(a, b)和cmp(b, a)都会返回true这就违反了严格弱序的规则。我见过不少人在这里翻车程序在本地跑没问题但提交上去就报错往往就是因为比较函数写得不规范。3.2 并列排名的计算方法并列排名的计算是这道题的一个重点。规则是这样的如果当前考生的成绩和前一个考生的成绩相同那么他们的排名相同否则当前考生的排名就是他在数组中的下标加1。用代码表示就是for (int i 0; i students.size(); i) { if (i 0 students[i].score students[i-1].score) { students[i].rank_all students[i-1].rank_all; } else { students[i].rank_all i 1; } }这个逻辑很直观如果成绩和前一个人一样就继承前一个人的排名否则排名就是当前的位置加1。考场内排名的计算也是同样的逻辑只不过需要先按照考场分组然后在每个考场内部排序。这里有个容易出错的地方排序的顺序。在计算考场内排名之前必须确保同一个考场内的考生是按照成绩从高到低、考号从小到大的顺序排列的。如果顺序不对计算出来的排名就是错的。3.3 多关键字排序的实现技巧这道题涉及到了多关键字排序先按成绩降序再按考号升序。在C中实现多关键字排序有两种常见方法。第一种方法是在比较函数里写多个if-else分支就像我前面写的那样。这种方法直观易懂适合关键字不多的情况。第二种方法是利用tuple或者pair的默认比较规则。比如可以把成绩取负然后和考号组成一个pair这样默认的排序规则就是先按成绩降序因为取了负再按考号升序。不过这种方法可读性稍差我一般还是用第一种方法。还有一种情况是如果排序的关键字更多比如还要按考场号排序那比较函数就会变得更长。这时候可以考虑把多个关键字打包成一个tuple然后用tie来比较。不过对于这道题来说两个关键字就够了不需要那么复杂。3.4 考场内排名的分组处理考场内排名的处理稍微麻烦一点因为需要按照考场分组。我的做法是这样的先把所有考生按照考场号排序同一个考场内的考生按照成绩降序、考号升序排列。然后遍历排序后的数组对每个考场内的考生计算排名。具体来说可以这样做sort(students.begin(), students.end(), cmp_location); int local_rank 1; for (int i 0; i students.size(); i) { if (i 0 students[i].location ! students[i-1].location) { local_rank 1; // 新的考场排名重新从1开始 } if (i 0 students[i].location students[i-1].location students[i].score students[i-1].score) { students[i].rank_local students[i-1].rank_local; } else { students[i].rank_local local_rank; } local_rank; }这里的cmp_location函数需要先按考场号升序再按成绩降序最后按考号升序。这样就能保证同一个考场内的考生是连续排列的而且顺序是正确的。不过这样做有一个问题计算完考场内排名之后数组的顺序就变成了按考场号排列而不是按总排名排列。所以还需要再按照总排名重新排序一次才能输出。为了避免反复排序我一般会先把总排名和考场内排名都计算好存到结构体里然后再按照总排名的顺序排序一次最后输出。3.5 输出格式的细节把控输出格式看起来简单但也有一些容易忽略的地方。首先输出的第一行是总考生人数。这个直接输出students.size()就行。然后每一行的格式是考号、总排名、考场号、考场内排名。中间用空格分隔。这里需要注意的是考场号是从1开始的不是从0开始。所以在读入数据的时候就要把考场号记为1到N而不是0到N-1。另外输出的顺序是按照总排名从高到低。如果总排名相同按照考号从小到大。这个顺序其实就是我们第一次排序后的顺序所以如果我们在计算完考场内排名之后重新按照总排名的规则排序一次就可以直接输出了。还有一个细节输出的时候不要有多余的空格。有些人在每行末尾多打了一个空格虽然一般不会影响判题但养成好习惯总是好的。4. 完整实操过程与核心代码实现4.1 数据读入与预处理先来看数据读入的部分。我用一个vector来存储所有考生同时记录每个考生的考场号。#include iostream #include vector #include algorithm #include string using namespace std; struct Student { string id; int score; int location; int rank_all; int rank_local; }; int main() { int N; cin N; vectorStudent students; for (int loc 1; loc N; loc) { int K; cin K; for (int i 0; i K; i) { Student s; cin s.id s.score; s.location loc; students.push_back(s); } } // 后续处理... return 0; }这段代码很直接外层循环遍历每个考场内层循环读取每个考生的信息。考场号从1开始依次递增。这里有个小优化可以提前用students.reserve()预留空间避免vector反复扩容。不过对于PAT的题目来说数据量一般不会太大不预留也没关系。4.2 总排名计算与排序实现接下来计算总排名。先按照总排名的规则排序然后遍历计算排名。bool cmp_all(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; } // 在main函数中 sort(students.begin(), students.end(), cmp_all); for (int i 0; i students.size(); i) { if (i 0 students[i].score students[i-1].score) { students[i].rank_all students[i-1].rank_all; } else { students[i].rank_all i 1; } }这段代码的逻辑很清晰先排序然后遍历计算排名。排序保证了成绩高的在前面成绩相同的按考号升序排列。计算排名时如果成绩和前一个人相同就继承前一个人的排名否则排名就是当前位置加1。4.3 考场内排名的分组计算考场内排名的计算需要先按考场分组然后在每个考场内部排序。bool cmp_local(const Student a, const Student b) { if (a.location ! b.location) return a.location b.location; if (a.score ! b.score) return a.score b.score; return a.id b.id; } // 在main函数中 sort(students.begin(), students.end(), cmp_local); int local_rank 1; for (int i 0; i students.size(); i) { if (i 0 students[i].location ! students[i-1].location) { local_rank 1; } if (i 0 students[i].location students[i-1].location students[i].score students[i-1].score) { students[i].rank_local students[i-1].rank_local; } else { students[i].rank_local local_rank; } local_rank; }这里的逻辑稍微复杂一点。首先排序保证了同一个考场的考生是连续排列的而且每个考场内部是按照成绩降序、考号升序排列的。然后遍历数组如果当前考生和上一个考生不在同一个考场就把local_rank重置为1。接着如果当前考生和上一个考生在同一个考场且成绩相同就继承上一个考生的考场内排名否则考场内排名就是local_rank。最后local_rank递增。这里有个细节local_rank的递增是在判断之后进行的。也就是说如果当前考生和上一个考生成绩相同local_rank仍然会递增但当前考生的排名继承的是上一个考生的排名。这样下一个考生的排名就会跳过被并列的名次。比如如果两个人并列第1那么local_rank会变成3下一个人的排名就是3而不是2。这正好符合并列排名的规则。4.4 最终排序与输出计算完总排名和考场内排名之后还需要按照总排名的顺序重新排序一次然后输出。sort(students.begin(), students.end(), cmp_all); cout students.size() endl; for (int i 0; i students.size(); i) { cout students[i].id students[i].rank_all students[i].location students[i].rank_local endl; }这里重新用cmp_all排序保证了输出的顺序是按照总排名从高到低总排名相同则按考号升序。然后依次输出每个考生的信息。4.5 完整代码整合与测试把上面的代码整合起来就是完整的解题代码#include iostream #include vector #include algorithm #include string using namespace std; struct Student { string id; int score; int location; int rank_all; int rank_local; }; bool cmp_all(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; } bool cmp_local(const Student a, const Student b) { if (a.location ! b.location) return a.location b.location; if (a.score ! b.score) return a.score b.score; return a.id b.id; } int main() { int N; cin N; vectorStudent students; for (int loc 1; loc N; loc) { int K; cin K; for (int i 0; i K; i) { Student s; cin s.id s.score; s.location loc; students.push_back(s); } } // 计算总排名 sort(students.begin(), students.end(), cmp_all); for (int i 0; i students.size(); i) { if (i 0 students[i].score students[i-1].score) { students[i].rank_all students[i-1].rank_all; } else { students[i].rank_all i 1; } } // 计算考场内排名 sort(students.begin(), students.end(), cmp_local); int local_rank 1; for (int i 0; i students.size(); i) { if (i 0 students[i].location ! students[i-1].location) { local_rank 1; } if (i 0 students[i].location students[i-1].location students[i].score students[i-1].score) { students[i].rank_local students[i-1].rank_local; } else { students[i].rank_local local_rank; } local_rank; } // 按总排名排序并输出 sort(students.begin(), students.end(), cmp_all); cout students.size() endl; for (int i 0; i students.size(); i) { cout students[i].id students[i].rank_all students[i].location students[i].rank_local endl; } return 0; }这段代码可以直接提交到PAT平台上。我实测过对于题目给出的测试数据输出是完全正确的。5. 常见问题与排查技巧实录5.1 排序结果不符合预期怎么办这是最常见的问题。排序结果不对通常有以下几个原因第一比较函数写错了。比如把写成了或者把考号的比较方向搞反了。检查的方法是拿两个考生手动模拟一下比较函数的行为看看结果是否符合预期。第二比较函数违反了严格弱序。比如用了或导致相等的元素之间比较结果不一致。这种情况下sort函数的行为是未定义的可能会崩溃也可能会产生奇怪的排序结果。第三排序的关键字顺序搞错了。比如应该先按成绩排序再按考号排序但代码里写反了。这种情况下排序结果看起来可能差不多但在某些测试点上会出错。排查方法先用小数据量测试手动验证排序结果。如果小数据量没问题再逐步增加数据量看看问题出在哪里。5.2 并列排名计算错误的排查并列排名计算错误通常是因为排序顺序不对或者排名计算的逻辑有问题。如果排序顺序不对比如成绩相同的考生没有按照考号升序排列那么计算出来的排名可能会错乱。检查的方法是在计算排名之前先输出排序后的数组看看顺序是否正确。如果排名计算的逻辑有问题比如在继承前一个人的排名时没有检查是否在同一个考场那么考场内排名就会出错。检查的方法是拿一个有多人并列的测试用例手动模拟一下排名计算的过程看看结果是否符合预期。5.3 考场内排名与总排名冲突的处理有时候考场内排名和总排名的计算会互相干扰。比如在计算考场内排名时把数组的顺序改变了导致后面计算总排名时出错。解决的方法是先计算总排名再计算考场内排名最后重新按总排名排序。这样两个排名的计算互不干扰最后输出的时候也是正确的顺序。如果你在计算考场内排名时发现总排名的数据被覆盖了那可能是因为你在排序时把整个结构体都重新排列了导致之前计算的总排名丢失。解决的方法是在计算考场内排名之前先把总排名的数据保存下来或者确保排序不会影响到已经计算好的排名。5.4 输出格式错误的常见原因输出格式错误通常有以下几个原因第一考场号从0开始。题目要求考场号从1开始如果你在读入数据时用了0-based的索引输出就会出错。第二每行末尾多了空格。虽然大多数判题系统会忽略行末空格但有些严格的系统会判错。建议在输出时注意不要多打空格。第三输出顺序不对。题目要求按照总排名从高到低输出如果输出顺序不对即使每个考生的信息都正确也会被判错。第四考号的前导零丢失。如果用整数存储考号输出时可能会丢失前导零。用string存储考号可以避免这个问题。5.5 性能优化与大数据量测试虽然PAT的题目一般不会卡时间但如果数据量特别大还是需要注意性能。首先避免不必要的拷贝。在比较函数中使用const引用避免拷贝结构体。其次减少排序次数。这道题需要排序三次总排名一次、考场内排名一次、最终输出一次如果能在一次排序中完成多个任务就可以减少排序次数。不过对于这道题来说三次排序已经足够了不需要过度优化。最后使用快速IO。如果数据量特别大可以用scanf/printf代替cin/cout或者关闭cin/cout的同步。不过在PAT中一般不需要这么做。5.6 常见问题速查表问题现象可能原因解决方法排序结果不对比较函数写错检查比较函数的逻辑确保符合严格弱序并列排名错误排序顺序不对确保排序时考虑了所有关键字考场内排名错误分组逻辑有问题检查是否在切换考场时重置了排名输出格式错误考场号从0开始确保考场号从1开始编号考号前导零丢失用整数存储考号改用string存储考号程序崩溃比较函数违反严格弱序避免使用或只用或运行超时数据量太大减少排序次数使用快速IO5.7 我踩过的那些坑第一次做这道题的时候我在比较函数里用了结果程序在本地跑没问题提交上去就报错。后来查了半天才发现是比较函数的问题。从那以后我写比较函数都会特别注意只用和绝不用和。还有一次我在计算考场内排名时忘记在切换考场时重置local_rank导致第二个考场的排名从第一个考场的排名继续累加。这个bug很隐蔽因为如果只有一个考场程序是完全正确的。只有在多个考场的情况下才会出错。另外我一开始用整数存储考号结果输出的时候前导零全丢了。后来改成string问题就解决了。虽然题目里的考号是13位数字用long long也能存下但用string更保险也方便输出。最后关于输出顺序我一开始是先按考场内排名排序然后直接输出结果顺序完全乱了。后来才意识到输出必须按照总排名的顺序所以需要在计算完考场内排名之后重新按总排名排序一次。6. 重写sort函数的思路与进阶技巧6.1 为什么要重写sort函数有人可能会问C的sort函数已经很好用了为什么还要重写其实这里说的“重写”并不是说要自己实现一个排序算法而是说自定义比较函数让sort按照我们的规则来排序。在PAT考试中自定义比较函数是必须掌握的技能。因为题目往往要求按照多个关键字排序而默认的排序规则无法满足需求。所以学会写比较函数是解决这类问题的关键。6.2 用lambda表达式简化比较函数除了写独立的比较函数还可以用lambda表达式来简化代码。比如sort(students.begin(), students.end(), [](const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; });lambda表达式的好处是可以把比较逻辑直接写在sort调用的地方不需要额外定义一个函数。对于简单的比较逻辑这样写更简洁。但如果比较逻辑比较复杂或者需要在多个地方复用还是定义一个独立的函数更好。6.3 用tuple实现多关键字排序如果排序的关键字很多比较函数会变得很长。这时候可以用tuple来简化sort(students.begin(), students.end(), [](const Student a, const Student b) { return make_tuple(-a.score, a.id) make_tuple(-b.score, b.id); });这里的技巧是把成绩取负这样默认的升序排序就变成了降序。然后和考号组成一个tupletuple的默认比较规则就是先比较第一个元素如果相同再比较第二个元素。这样就能实现多关键字排序而且代码很简洁。不过这种方法有一个限制tuple里的元素类型必须支持比较运算符。对于string和int来说这是没问题的。但如果有关键字是自定义类型就需要自己定义比较运算符了。6.4 稳定排序与不稳定排序的选择C的sort函数是不稳定排序也就是说相等的元素在排序后的相对顺序是不确定的。如果题目要求相等的元素保持原来的顺序就需要用stable_sort。在这道题中我们通过比较函数已经明确了相等元素的顺序按考号升序所以用sort就够了。但如果比较函数中没有考虑所有关键字导致有些元素相等那么用stable_sort可以保证它们的相对顺序不变。不过stable_sort的时间复杂度是O(n log^2 n)比sort的O(n log n)要慢。所以如果不需要稳定排序还是用sort更好。6.5 自定义排序的边界情况处理在写比较函数时需要注意一些边界情况。第一所有关键字都相等。这种情况下比较函数应该返回false表示两个元素相等。如果返回true就会违反严格弱序。第二浮点数比较。如果成绩是浮点数不能直接用比较而应该用一个很小的epsilon来判断。不过这道题的成绩是整数不需要考虑这个问题。第三空数组或单元素数组。这种情况下排序不会做任何操作但比较函数仍然需要是正确的。所以即使数据量很小也要确保比较函数的逻辑没问题。6.6 从这道题延伸出的排序技巧这道题虽然只是一道25分的题目但它涉及到的排序技巧可以应用到很多场景。比如在数据库查询中经常需要按照多个字段排序。这时候就可以用类似的方法把多个字段组合成一个排序键。再比如在推荐系统中需要对物品按照多个指标排序如点击率、转化率、价格等。这时候也可以用自定义比较函数来实现。总之掌握多关键字排序的技巧对于解决实际问题是非常有帮助的。而PAT的这道题正好是一个很好的练习。7. 一些实操心得与建议做这道题的时候我最大的体会是不要急着写代码先把思路理清楚。这道题的逻辑其实不复杂但细节很多。如果一开始就埋头写代码很容易在某个细节上卡住然后反复调试浪费很多时间。我的建议是先拿一张纸把整个流程画出来数据怎么读、怎么排序、怎么计算排名、怎么输出。把每个步骤都写清楚然后再开始写代码。这样写出来的代码逻辑清晰不容易出错。另外多写测试用例。这道题的测试用例可以很简单比如两个考场每个考场两个人成绩有并列的情况。通过手动计算预期输出然后和程序输出对比可以快速发现bug。还有注意代码的可读性。虽然PAT考试只看结果但代码写得清晰调试起来会容易很多。比如变量名要有意义比较函数要加注释关键步骤要写清楚意图。这些习惯在考试中可能看不出好处但在实际工作中会大大提高效率。最后不要怕重写。如果发现代码有问题不要试图在原来的基础上修修补补而是直接重写。因为修补往往会让代码越来越乱最后自己也看不懂。重写虽然花时间但能保证代码的质量。我在实际编码中的体会是这道题虽然不难但很考验基本功。如果你能一次通过说明你的排序和结构体操作已经很熟练了。如果不能也没关系多练几遍把每个细节都搞清楚以后遇到类似的问题就能轻松解决了。
阅读完成 · 觉得有帮助？
：从原理到实战的WAF绕过与防御指南)
