★ FEATURED ARTICLE 1. 从“排名汇总”这道题说起为什么它值得反复琢磨PAT排名汇总这道题在数据结构与算法的练习体系里属于那种“看起来不难写起来处处是坑”的典型。我第一次碰到它的时候扫了一眼题目描述心想不就是把几个考点的成绩合并起来排个序吗能有多复杂。结果真正动手写的时候光是处理同分并列的排名规则就来回改了三遍更别提跨考点合并之后名次怎么重新计算的问题。这道题的核心场景是这样的有若干个考点每个考点有若干考生每个考生有考号和成绩。你需要先把每个考点内部的考生按成绩排好名次然后再把所有考点的考生合并到一起按成绩重新排一次总名次。输出的时候既要体现考生的总排名又要体现该考生在自己所在考点内的排名。同分的情况下排名并列但并列之后下一个名次需要跳过相应的位次。为什么说这道题值得反复琢磨因为它几乎涵盖了排序类题目的所有核心考点多级排序条件的优先级设计、并列名次的处理逻辑、跨组数据的合并与重新编号、排序稳定性的影响以及自定义比较函数时容易忽略的边界情况。你把这几个点吃透了后面遇到类似的“分组排序再合并”的题目基本就是换个壳子的事情。另外这道题在输入规模上也有讲究。考点的数量和每个考点的考生数量都可能不小如果你用冒泡或者选择排序那种O(n²)的算法大概率会超时。所以必须用O(n log n)级别的排序算法而C里最顺手的就是std::sort配合自定义比较函数。但问题来了——std::sort默认是不稳定的当两个考生成绩相同时它们的相对顺序是不确定的。这在排名汇总的场景下会不会出问题答案是只要你正确处理了并列名次排序是否稳定其实不影响最终结果的正确性但会影响输出的确定性。这一点我在后面会详细展开。提示这道题虽然来自在线评测平台但它背后的“分组排序合并重排”模式在实际工作中非常常见比如电商场景下各仓库的库存排序再汇总、多地区销售业绩的合并排名等。所以花时间把它彻底搞懂绝对不亏。2. 题目要求的精确拆解别急着写代码先把规则吃透2.1 输入输出格式的细节确认在动手写任何代码之前我习惯先把题目的输入输出格式逐字读一遍把每个字段的含义和约束条件标注清楚。这道题的输入结构大致是这样的第一行给出考点的总数接着每个考点的数据块依次排列每个数据块的第一行是该考点的考生人数随后每行是一个考生的考号和成绩。输出方面第一行需要输出所有考生的总人数然后按照总排名从高到低输出每个考生的信息包括考号、总排名、考点编号、考点内排名。这里有一个很容易被忽略的点输出顺序是总排名优先而不是按考点分组输出。也就是说你需要把所有考点的考生混在一起重新排序而不是先输出考点一再输出考点二。我见过不少人在这一步翻车原因就是没有仔细看输出要求习惯性地按考点分组处理完就直接输出了。结果格式完全不对白白浪费一次提交机会。所以我的建议是在读题阶段就用笔把输入输出的结构画出来标注清楚每个字段的来源和计算方式。2.2 排名规则的精确定义排名规则是这道题的核心难点。具体来说它遵循的是“标准竞赛排名”规则成绩相同的考生名次并列但并列会占用后续名次的位置。举个例子如果成绩分别是100、95、95、90那么排名就是1、2、2、4。注意最后一个是4而不是3因为两个并列第2已经占用了第2和第3两个位置。这个规则在考点内排名和总排名中都要一致地应用。很多人在处理考点内排名的时候逻辑是对的但到了总排名就忘了同样处理导致结果出错。我的做法是写一个通用的排名计算函数接收一个已经按成绩降序排列的考生列表然后依次遍历遇到成绩变化就更新当前名次为当前索引加一否则沿用上一个名次。这样无论是对考点内还是总排名逻辑都是统一的。还有一个细节当成绩相同时考号小的应该排在前面吗题目通常不会明确要求这一点但为了输出的确定性我建议在比较函数中加入考号作为次级排序条件。这样即使成绩相同输出顺序也是稳定的、可预期的。2.3 数据规模的隐含约束虽然题目没有在描述中直接给出数据规模的上限但从“25分”的难度定位和常见的评测数据设计来看考生总数很可能在万级别甚至更高。这意味着你不能用O(n²)的排序算法也不能在每次插入时做线性扫描。另外考点的数量也可能不少所以存储结构需要能够方便地按考点分组同时又能快速地合并成一个全局列表。我通常会用vector的嵌套结构来存储外层vector表示考点内层vector表示该考点的考生。合并的时候直接把所有内层vector拼接起来即可。注意拼接之后一定要重新排序并重新计算总排名不能直接沿用考点内的排名。这是两套独立的排名体系必须分别计算。3. 整体思路设计从分组排序到合并重排的完整链路3.1 数据结构的选择与理由对于这道题我选择用结构体来表示考生信息包含考号、成绩、考点编号、考点内排名、总排名这几个字段。为什么用结构体而不是并行数组因为结构体能把一个考生的所有相关信息绑定在一起在排序和传递的时候不容易出错。并行数组虽然在某些场景下缓存友好性更好但在这种需要频繁交换和比较的场景下结构体的可读性和可维护性明显更优。存储结构方面我用一个二维的vector来保存所有考点的考生数据。外层vector的每个元素对应一个考点内层vector存储该考点的所有考生。这样做的好处是考点内排序的时候只需要操作对应的内层vector合并的时候再把所有内层vector的元素拷贝到一个全局vector中。全局vector用于最终的总排序和总排名计算。这里有一个小优化可以在合并之前先预留足够的空间避免多次扩容带来的性能损耗。虽然对于这道题来说这点开销可能无关紧要但养成好习惯总是没错的。3.2 考点内排序与排名计算考点内排序的目标是确定每个考生在该考点内的名次。步骤很直接先按成绩降序排序然后遍历排序后的列表按照前面说的并列规则计算名次。比较函数的设计是关键。我通常这样写如果成绩不同成绩高的排前面如果成绩相同考号小的排前面。第二个条件不是题目强制要求的但它能保证排序结果的确定性避免因为排序算法的不稳定性导致同一份代码在不同环境下输出不同的结果。计算名次的时候我用一个变量记录当前的名次值初始为1。遍历列表时如果当前考生的成绩和上一个考生相同就沿用上一个名次否则把名次更新为当前索引加一。这个逻辑简单但容易写错特别是索引和名次的对应关系建议在纸上画一遍再写代码。3.3 合并与总排名计算合并的过程就是把所有考点的考生收集到一个全局列表中。这里要注意合并之后每个考生的考点编号和考点内排名不能丢因为最终输出需要这些信息。总排名的计算逻辑和考点内排名完全一样只是作用在全局列表上。排序的比较函数也保持一致先比成绩再比考号。排序完成后按照同样的并列规则计算总排名。这里有一个容易踩的坑如果你在考点内排序之后直接修改了考生在列表中的位置然后合并的时候又依赖某种顺序可能会导致数据混乱。我的建议是考点内排序和排名计算完成后把结果保存好合并的时候直接拷贝不要在合并过程中做任何额外的排序或修改。3.4 输出格式的精确控制输出的时候先输出总人数然后按总排名从高到低输出每个考生的信息。注意输出的顺序是总排名顺序而不是考点分组顺序。每个考生的信息包括考号、总排名、考点编号、考点内排名字段之间用空格分隔。我在输出这一步踩过的坑主要是格式问题有时候多输出一个空格有时候少输出一个换行都会导致评测不通过。所以建议在本地测试的时候把输出结果和预期结果逐字符对比确保格式完全一致。4. 重写sort比较函数那些你必须知道的细节4.1 为什么需要自定义比较函数std::sort默认使用operator进行升序排序但我们的需求是按成绩降序排列所以必须提供自定义的比较函数。比较函数的签名通常是接收两个常量引用返回一个布尔值表示第一个参数是否应该排在第二个参数之前。这里有一个常见的误解很多人以为比较函数返回true表示“第一个比第二个大”其实不是。它返回的是“第一个是否应该排在第二个前面”。在降序排序的场景下如果第一个的成绩高于第二个应该返回true表示第一个排在前面。4.2 比较函数的严格弱序要求std::sort对比较函数有一个硬性要求必须满足严格弱序。简单来说就是比较函数不能出现自相矛盾的情况。比如你不能让cmp(a, b)和cmp(b, a)同时返回true也不能让cmp(a, a)返回true。这个要求在实际写代码时很容易被违反特别是当比较逻辑涉及多个字段的时候。比如如果你先比较成绩成绩相同再比较考号但考号的比较逻辑写反了就可能导致严格弱序被破坏。一旦违反了这个要求std::sort的行为是未定义的可能崩溃也可能产生错误的排序结果。我的经验是写完比较函数之后用几个边界用例手动验证一下两个完全相同的元素、两个成绩相同但考号不同的元素、两个成绩不同的元素。确保比较函数在这些情况下都返回合理的结果。4.3 并列名次对排序稳定性的影响前面提到过std::sort是不稳定的。这意味着如果两个考生成绩相同它们在排序后的相对顺序是不确定的。这会影响最终结果吗答案是只要你正确计算了并列名次排序是否稳定不影响名次的正确性。因为成绩相同的考生名次相同无论它们谁排在前面名次值都是一样的。但是输出的顺序会受到影响。如果评测系统对输出顺序有严格要求比如要求考号小的排在前面那么你就需要在比较函数中加入考号作为次级排序条件来保证输出的确定性。我个人的做法是始终加入考号作为次级条件这样无论排序算法是否稳定输出都是确定的。这在实际工作中也是一个好习惯因为确定性意味着可复现可复现意味着容易调试。4.4 比较函数的性能考量比较函数会被std::sort调用很多次所以它的性能直接影响整体运行时间。在比较函数中应该尽量避免不必要的操作比如字符串比较、内存分配等。对于这道题来说比较的字段都是整数所以性能瓶颈不在这里。但如果你在比较函数中使用了引用传递而不是值传递可以避免不必要的拷贝。另外把比较函数写成内联的或者用lambda表达式也有助于编译器优化。// 比较函数的典型写法 bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; }这段代码看起来简单但它满足了严格弱序的要求成绩不同时按成绩降序成绩相同时按考号升序。两个条件互斥且完备不会出现矛盾。5. 实操中容易翻车的几个关键点5.1 名次计算的索引陷阱计算名次的时候最容易犯的错误是把索引和名次搞混。索引是从0开始的名次是从1开始的。如果你直接用索引作为名次第一个考生的名次就是0这显然不对。正确的做法是遍历的时候维护一个currentRank变量初始值为1。每遇到一个成绩不同的考生就把currentRank更新为当前索引加一。这样第一个考生的名次是1第二个如果成绩不同就是2如果成绩相同就还是1。还有一个细节更新currentRank的时机是在发现成绩变化时而不是在每次遍历时。如果你在每次遍历时都更新那么成绩相同的考生就会得到不同的名次这不符合并列规则。5.2 跨考点合并时的数据一致性合并的时候你需要把每个考点的考生拷贝到全局列表中。这里要注意拷贝之后每个考生的考点编号和考点内排名必须保持不变。如果你在拷贝过程中不小心修改了这些字段最终输出就会出错。我的做法是在考点内排序和排名计算完成后把结果固定下来合并的时候只做拷贝不做任何修改。全局排序和总排名计算只影响总排名字段不影响其他字段。另外全局列表的顺序在排序后会改变但这不影响考点内排名因为考点内排名已经作为数据的一部分被保存下来了。5.3 输出顺序与格式的常见错误输出的时候最常见的错误是顺序不对。题目要求按总排名从高到低输出但有些人会按考点分组输出或者按考号顺序输出。这些都不符合要求。格式方面要注意每个字段之间的分隔符和行尾的换行。有些评测系统对行尾空格敏感所以最好确保每行最后一个字段后面没有多余的空格。我通常会在本地用一个小脚本把输出结果和预期结果做逐行对比这样能快速定位格式问题。5.4 大数据量下的性能优化如果考生总数很大比如十万级别那么排序的性能就很重要了。std::sort的平均时间复杂度是O(n log n)对于十万级别的数据来说通常在一秒以内可以完成。但如果你在比较函数中做了很多额外的操作或者用了低效的数据结构就可能超时。优化的方向包括减少比较函数中的操作、避免不必要的拷贝、使用预留空间减少扩容次数。另外如果考点数量很多但每个考点的考生很少可以考虑先把所有考生合并再统一排序而不是先分考点排序再合并。不过这道题要求输出考点内排名所以分考点排序是必须的。6. 从这道题延伸出去分组排序合并模式的通用解法6.1 同类问题的识别特征“分组排序再合并”这种模式在算法题中出现的频率很高。它的典型特征是数据天然分为若干组每组需要独立排序和编号然后所有组的数据需要合并后重新排序和编号。除了PAT排名汇总类似的还有多班级成绩排名、多地区销售排名、多仓库库存排序等。识别出这种模式之后你就可以套用一套通用的解题框架分组存储、组内排序、组内编号、合并、全局排序、全局编号、按全局编号输出。这套框架的核心在于排序和编号的逻辑要统一不能组内一套、全局另一套。6.2 通用解题框架的伪代码1. 读取所有组的数据存储为二维结构 2. 对每个组 a. 按比较函数排序 b. 遍历排序后的列表计算组内排名 3. 将所有组的元素合并到一个全局列表 4. 对全局列表按同样的比较函数排序 5. 遍历全局列表计算全局排名 6. 按全局排名顺序输出结果这个框架看起来简单但每一步都有细节需要注意。比如第2步和第5步的比较函数必须一致否则组内排名和全局排名的依据就不同了。再比如第3步合并的时候要确保每个元素的组内排名已经被正确计算并保存。6.3 不同变体的处理策略有些变体可能会增加额外的要求比如组内排名和全局排名的规则不同或者输出格式有特殊要求。遇到这种情况核心思路不变只需要调整对应的步骤即可。还有一种变体是动态分组也就是说组的信息不是预先给定的而是根据数据中的某个字段动态划分的。这种变体需要先用哈希表或排序的方式把数据分组然后再套用上面的框架。我在实际工作中遇到过一个类似的场景多个数据源的商品价格需要分别排序后合并最终按统一排名展示。用的就是这套框架只是把考生换成了商品把成绩换成了价格。逻辑完全一样改改变量名就能跑。6.4 从解题到工程实践的思维迁移这道题虽然是一道算法练习题但它背后的思维模式在工程实践中非常有用。比如在电商系统中不同仓库的库存需要分别排序然后合并后按统一规则展示在数据分析中不同维度的指标需要分别排名然后合并后生成综合排名。关键是要理解“分组”和“合并”这两个动作的本质分组是为了在局部范围内建立秩序合并是为了在全局范围内建立秩序。两套秩序可以独立存在但最终呈现给用户的是全局秩序。理解了这一点你就能灵活应对各种变体。7. 我在反复练习中总结的几条实战心得第一先写测试用例再写代码。这道题的边界情况比较多比如所有考生成绩相同、只有一个考生、考点内只有一个考生等。提前把这些用例准备好写完代码直接跑能省下大量调试时间。第二比较函数和排名函数要分开写。比较函数只负责定义排序规则排名函数只负责根据排序结果计算名次。两者职责分明修改其中一个不会影响另一个。第三输出格式用脚本验证。不要相信自己的眼睛人眼对空格和换行的敏感度很低。写个小脚本做逐字符对比几秒钟就能确认格式是否正确。第四性能问题优先怀疑比较函数。如果超时了先检查比较函数里有没有不必要的操作。大多数情况下优化比较函数就能解决问题。第五多组测试数据要覆盖极端情况。比如所有考生同分、所有考点人数相同、某个考点人数为零等。这些情况在真实评测中出现的概率不低提前覆盖能避免意外翻车。提示如果你在练习过程中发现自己的代码在本地能过但提交后出错大概率是边界情况没覆盖到。建议把题目描述再读一遍逐条对照自己的代码看看有没有遗漏的约束条件。最后分享一个我个人的习惯每次做完一道排序类的题目我都会把比较函数和排名函数的写法整理到一个模板文件里。下次遇到类似的题目直接复制过来改改变量名就能用。这个习惯让我在练习和工作中都省了不少时间推荐你也试试。
阅读完成 · 觉得有帮助？
