★ FEATURED ARTICLE 第一次刷到 PAT 乙级 1015“德才论”这道题的人多半会被它那长长的题干和一堆古文词汇唬住又是“才德全尽”又是“德胜才”还没开始写代码就先做了五分钟阅读理解。但拆开来看它其实是 PAT 乙级排序专题里非常典型的一道结构体排序题——把一组考生先分层、再排名考察的就是读题能力和多关键字排序的基本功。这篇文章就把这道 25 分题从题目拆解、思路设计、完整代码到实际提交中的坑一次讲透适合正在备考 PAT 乙级、刚学完结构体和 sort 想找实战题的读者也适合想复习多条件排序的人。1. 德才论到底在考什么把长题干拆成可计算的规则1.1 先看懂录取门槛不是总分过线而是德、才分别过线题目输入会给出三个数字考生人数 N、最低录取分数线 L、优先录取线 H。一开始很多人会习惯性地把“最低分数线”理解成总分最低线于是先算出德分加才分的总分再拿总分和 L 比较。这是一个非常容易踩的思维陷阱。实际上这道题说的是德分和才分两门都必须分别达到 L只要有一门低于 L这位考生就直接淘汰连参与排序的资格都没有。举个例子说明就更清楚了。假设 L60H80有下面几位考生考生编号德分才分德分L才分L能否进入排名A8590是是能B9070是是能C8050是否不能淘汰D7572是是能E5595否是不能淘汰特别是 C 和 E 这种“偏科”的考生哪怕两门加起来不算低甚至某一门很高只要另一门没过 L照样不在输出列表里。这一步筛选是整个题目的第一个关键门槛很多人排序规则写对了最后却因为没先做资格过滤而差几分。1.2 四类划分从古文描述到 if-else 条件通过 L 这道门槛之后题目会按德分和才分与 H 的关系把考生分成四类。题干里那些“才德全尽”“德胜才”“才德兼亡”之类的词本质上只是为了增加一点背景故事真正写代码时不需要咬文嚼字只看条件。四类规则整理成表类别通俗理解条件前提德分和才分均 L第 1 类德才双高de H 且 cai H第 2 类德高分但才分相对低de H 且 cai H第 3 类德才都不到 H但德分不低于才分de H 且 cai H 且 de cai第 4 类其余达到 L 的考生前 3 类都没命中这里有一个非常容易出错的细节第 3 类里的条件是“德分不低于才分”注意是不低于也就是包含德分等于才分的情况。如果你把条件写成 de cai 而不是 de cai那么那些德分和才分恰好相等的考生会被错误地丢进第 4 类。这种错误在样例数据里可能看不出来因为样例不一定覆盖相等情形但评测数据集里一定会有结果就是白白丢分。1.3 同档内部的三级排序一道题里藏了三把尺子分类完成之后输出顺序要先按类别从 1 到 4 输出这是第一级排序。类别相同的考生再按以下规则排序总分高者在前总分就是德分加才分。总分相同德分高者在前。德分也相同准考证号小的在前。这三条规则合起来就是一组典型的“多关键字排序”。关键词优先级从高到低就是类别升序、总分降序、德分降序、准考证号升序。注意最后一条是升序有些人在前面写惯了降序到准考证号这里也顺手写个降序结果小号在后大号在前答案自然错。这道题的考点其实非常直白你能不能把自然语言描述的多条排序规则准确地翻译成一个比较函数。第 1 章把规则摸清楚之后后面写代码就只是例行公事了。2. 动手设计前先想清楚结构体、分类和比较器的思路推导2.1 记录一条考生信息需要存哪些字段既然要排序第一步肯定是设计一个结构体来保存每位考生的信息。最基本的是准考证号、德分、才分三个字段。但光有这三个还不够我建议在结构体里直接把两个“加工后的字段”也存下来一个是总分 total一个是类别 level。为什么要提前存因为排序的比较函数会被调用非常多次默认的 std::sort 复杂度是 O(N log N)而每次比较都去重新计算 total 或者重新分类等于把同样的事情重复做了几十万次。虽然这道题数据量下不至于卡到超时但这是一个非常不好的编程习惯。在读取每条记录时一次性算好 total 和 level之后比较器里只做字段之间的比较逻辑干净又高效。关于准考证号字段用什么类型有一个细节值得单独说。很多 OJ 题里的准考证号看起来是一串数字比如 1001、1002 这种。这种情况下用 int 存储完全够用输出时直接用 %d 打出来就行。但有些题目编号可能带前导零或者编号本身被当成字符串处理更保险那就应该用 char 数组或 string。一个实用的判断标准是如果输出样例里的编号是原样输出且没有前导零用 int 最简单如果你担心格式问题直接读成字符串一定不会错。我在下面的代码里先用 int 演示因为这样最贴合常见版本题目的做法。2.2 分类函数怎么写才不重不漏四类划分看起来是四个并列条件但写代码时一定要按优先级顺序依次判断。原因很简单第 1 类和第 2 类都要求德分达到 H第 3 类则要求德分和才分都低于 H这些条件在逻辑上有包含关系。如果顺序不当很容易把某些特殊组合分错类。具体来说判断逻辑应该这样写int level; if (de H cai H) { level 1; } else if (de H cai H) { level 2; } else if (de H cai H de cai) { level 3; } else { level 4; }理解这段代码的关键在于因为前面已经判断过 de H 的情况所以执行到第三个分支时当前记录必然满足 de H。但为了可读性我还是会把 de H 和 cai H 这两个条件原样写在第三个分支里这样别人读代码时不需要自己推导上下文一眼就能看出这一类的完整条件。有一个常见的疑问是如果某个考生德分不到 H才分却达到了 H比如 de70, cai90那他是哪一类按规则他不满足第 3 类因为第 3 类要求才分也低于 H他会被分到第 4 类。这类“偏科偏到才比德强”的考生确实只够第 4 档这一点在理解题意时容易被忽略。2.3 比较函数让 sort 明白“到底谁排在前面”C 的 std::sort 排序依据是第三个参数——比较函数。这个函数的语义是给定两个元素 a 和 b返回 true 表示 a 应该排在 b 前面返回 false 则反之。比较函数必须满足严格弱排序strict weak ordering通俗点说就是不能出现“a 排在 b 前面且 b 排在 a 前面”这种自相矛盾的情况。针对这道题的比较函数可以这样写bool cmp(const Rec a, const Rec b) { if (a.level ! b.level) return a.level b.level; if (a.total ! b.total) return a.total b.total; if (a.de ! b.de) return a.de b.de; return a.id b.id; }这段代码的写法和题目规则一一对应先比类别类别不同时直接返回 a.level b.level也就是类别编号小的排前面类别相同时比总分总分不同时总分大的排前面总分相同时比德分德分大的排前面最后剩下所有字段都相同时按准考证号小的排前面。注意每一层都用“不相等才比较”的方式写直到最后一层才直接返回 id 的大小比较。这种写法才是符合严格弱排序要求的。第 2 章把这些设计思路讲清楚后代码其实已经水到渠成。很多初学者喜欢一上来就写代码写到比较函数才发现自己没想清楚规则又回头改结构体白白浪费调试时间。先设计、后编码在这道题上能帮你省下大量不必要的返工。3. 完整代码逐段拆解一份能一次通过 OJ 的 C 实现3.1 输入处理与资格筛选先放一份完整可运行的代码再逐段说明里面每个关键点。#include cstdio #include vector #include algorithm using namespace std; struct Rec { int id; int de; int cai; int total; int level; }; bool cmp(const Rec a, const Rec b) { if (a.level ! b.level) return a.level b.level; if (a.total ! b.total) return a.total b.total; if (a.de ! b.de) return a.de b.de; return a.id b.id; } int main() { int N, L, H; scanf(%d%d%d, N, L, H); vectorRec arr; arr.reserve(N); for (int i 0; i N; i) { int id, de, cai; scanf(%d%d%d, id, de, cai); if (de L || cai L) continue; int level; if (de H cai H) level 1; else if (de H cai H) level 2; else if (de H cai H de cai) level 3; else level 4; Rec r; r.id id; r.de de; r.cai cai; r.total de cai; r.level level; arr.push_back(r); } sort(arr.begin(), arr.end(), cmp); printf(%d\n, (int)arr.size()); for (int i 0; i (int)arr.size(); i) { printf(%d %d %d\n, arr[i].id, arr[i].de, arr[i].cai); } return 0; }主流程非常清晰先读 N、L、H然后循环读每条记录。循环里第一件事就是资格筛选德分或才分低于 L 的考生直接 continue不会进入 arr。这里用 continue 而不是把考生塞进 vector 再过滤可以省掉无谓的存储也让后续排序的数据集天然都是合法记录。3.2 分类、入队与排序输出筛选通过后按第 2 章讲到的顺序算出 level同时算出 total把整条记录 push 进 arr。这里用 vector 存储的好处是自动管理长度最后要统计输出人数时直接用 arr.size() 就行。有一点值得注意代码里 Rec 结构体的字段顺序和 push 后访问的顺序保持一致这在逻辑上不会出问题但如果你用的是数组而不是 vector记得先确定最大容量。N 通常能到十万这个量级一个 Rec 包含 5 个 int也就是 20 字节十万条记录大约 2MB 内存完全不用紧张。排序完成后先输出人数再逐行输出每条记录。输出格式要特别注意编号、德分、才分之间是空格分隔每行结尾是换行。如果输出人数时忘了换行或者多打了一个空格都可能被判为格式错误。这种错误在 PAT 评测里同样会扣分甚至直接判 Wrong Answer。3.3 关于 IO 和内存的几个优化选择为什么这里用 scanf / printf 而不是 cin / cout三个字稳定性。在 N 比较大、单点测试数据量能达到十万级的时候cin / cout 在没有关闭同步的情况下可能会明显变慢。虽然可以用ios::sync_with_stdio(false)搭配cin.tie(nullptr)来提速但很多经常刷 OJ 的人已经习惯了直接上 scanf / printf省得在不同评测环境之间出现性能差异。arr.reserve(N) 这个调用也值得养成习惯。它提前给 vector 分配好容量避免在 push_back 过程中反复扩容、搬移数据。虽然不写这道题大概率也能过但这是大型数据下很实用的经验。如果想用 C 语言实现那么把 Rec 定义成 struct 数组用 qsort 也一样能过。不过 C 的 qsort 比较函数需要传入 void* 指针写起来更啰嗦不如 C 的 std::sort 直观。做题时间有限用自己最熟悉、最不容易出错的写法才是正道。4. 提交与踩坑记录我在实际刷题时撞过的三个典型错误4.1 第三类条件少了等号德才相等的考生全部错位这道题我第一次提交时并不是一次通过。当时我把第三类条件顺手写成了de cai自认为很合理结果输出结果和题目样例对比时发现凡是在样例里德分等于才分且都低于 H 的考生全被排到了第四类的区域。原因是第三类条件要求“德分不低于才分”这个“不低于”在数学上就是包含等于。丢掉等号后等于的情况就落进 else 分支进入第四类。排查这类问题比较高效的方法是把分类和排序分开验证。我当时临时写了一段调试代码把所有记录按“编号、德分、才分、算出来的 level”一行行打出来再拿同一组数据手工推一遍期望 level。手工推的时候第三类里的相等情况当场就暴露了。改掉这一个冒号样例和自测数据全部对上。提这个例子是想说分类条件里的边界词比如“不低于”“不低于”“超过”读题时一定要圈出来翻译成代码时一个字都不能含糊。4.2 比较器里出现“等于号直接返回 true”排序结果像猜谜另一个我见过很多次的错误是把比较函数写成这样bool cmp(Rec a, Rec b) { return a.total b.total; }看起来好像“总分高的排前面总分相等也不要紧”实际上这是错的。std::sort 依赖严格的弱排序比较器返回 true 表示“a 必须排在 b 前面”。如果a.total b.total那么两个总分相等的元素会同时满足cmp(a, b)true和cmp(b, a)true排序算法就会陷入自相矛盾。虽然不一定会崩溃但最终顺序不可预期。正确写法前面已经给过了每一层都用“不相等才参与比较”相等就跳到下一层。只有到最后一个无关紧要的字段时你才可以直接返回一个最终比较结果。如果你压根不在乎某个字段相等时的先后那最后一层返回 false 也可以。但在这道题里准考证号是题目明确要求的最终排序依据所以必须写return a.id b.id;。4.3 准考证号的输出格式补零问题和字符串比较的坑准考证号这块不同版本题目可能有不同表述。如果题目把它定义为整数比如 1001、1002 这种直接在输出时用%d就行。但如果题目规定了编号位数比如 8 位输出时可能需要补前导零这时候用printf(%08d, id)才能保证格式正确。反过来如果你把编号读成字符串输出倒是简单了但排序时会变成字典序比较。字典序和数字升序在位数不等的情况下会得出不同结果这就容易埋雷。我的建议是做题前先看输出样例确定编号是否带前导零。不带前导零就用 int带前导零或者位数不固定干脆用 string 存储排序时也按字符串字典序排因为题目这种情况下要求的就是字典序。还有一个更稳妥的做法是自定义一个“编号比较”函数确定题目到底按数值还是按字典序比较后再写避免在角落翻车。4.4 边界自测用 LH 和同分场景验证逻辑每次写完排序题我会习惯性地构造几个边界数据来验证而不是只跑一遍样例就提交。对这道题来说最值得测的边界是 LH。当 LH80 时德分 85 才分 70 的考生虽然按分类规则能算出 level2但因为才分达不到 L80在资格筛选阶段就会被淘汰不会出现在输出里。另一个边界是德分和才分全部相同的多名考生比如有三位考生的德分都是 60、才分都是 60、总分都是 120那么输出时他们必须按准考证号从小到大的顺序出现。如果排序结果不是这个顺序说明比较器最后一级没有生效。这类自测不需要太多数据构造 5 到 10 条记录手写出期望输出再和程序输出逐行比对基本就能把逻辑漏洞找齐全。很多评测点故意设计成这种边界情况自己在本地先踩一遍提交时才不会懵。5. 题目背后的通用方法论从“德才论”到任意多级排序问题5.1 多关键字排序的建模套路先把优先级链画出来刷完德才论之后你会发现它其实代表了一类非常常见的题型先筛选、再分档、最后按多个优先级排序。不只是 PAT很多排序业务场景也是这个套路。比如给候选人排序先按是否通过初试分档同档再按笔试分数笔试相同按面试分数面试再相同按报名先后。这和德才论的结构完全一致。通用的建模步骤可以总结成四步。第一步明确淘汰条件把不合格的数据先过滤掉。第二步把剩余数据分成互斥的若干档档与档之间没有交叉。第三步画出每档内部的优先级链从主排序字段一直排到唯一标识字段。第四步把优先级链翻译成比较函数每一层都用“不相等才比较”的写法最后一层兜底。只要按照这个顺序来哪怕是再复杂的排序规则也能平铺成一段清晰的代码。如果你想把比较函数设计得更可读可以给每一层单独注释说明当前这一层比的是哪个字段、为什么这个字段优先于下一个字段。看起来只是多写几行注释但在实际项目里这能让下一个接手的人省掉大量猜测。5.2 sort、stable_sort、qsort到底该怎么选德才论这类题用 std::sort 就够了。std::sort 是不稳定排序意思是排序前后相等元素的相对顺序不保证。但注意这里说的“相等”是指比较器认为相等而不是题目里某个字段相等。比较器写完整之后所有元素之间都有明确的先后关系stability 其实已经无所谓了。那 stable_sort 什么时候用举个例子你有一批按时间录入的数据想按分数从高到低排序同时希望分数相同的人保持原来的录入顺序。这时候如果比较器只写“分数高的排前面”std::sort 会破坏相对顺序而 std::stable_sort 能保留原始相对顺序。这是稳定的真正意义。做题时还有一个建议不要把希望寄托在“数据量小所以 sort 变成插入排序实际是稳定的”这种实现细节上。不同标准库的实现可能不同稳定与否并不由数据量决定只由算法本身的特性决定。写全比较器永远是最可控的方案。5.3 看到“第几类再排序”的题以后怎么下手以后再遇到类似“按 ABC 分类每一类内部再排序”的题目可以按下面这个思路快速建立解题框架先圈出题目的资格条件再圈出分类条件最后圈出排序关键字。资格条件决定哪些数据根本不用进容器分类条件决定分几档、档之间怎么排排序关键字决定档内怎么比。这三个问题想清楚之后代码骨架很快就能画出来剩下的是结构体和比较器的机械实现。德才论本身只有 25 分算不上难题但它非常考验读题仔细程度和边界条件的敏感度。我个人的体会是这种题不要急着写代码先在草稿纸上把分类表格和优先级链画出来再动手。画完表格代码反而是整个流程里最轻松的一部分。最后分享一个我刷题时的小习惯每道排序题提交前都检查一遍比较器的每一层是不是都用了“不相等才比较”的方式以及最后一层是否覆盖了所有字段。这两点检查完排序题至少能避掉一半的隐性错误。德才论这道题虽然只是 PAT 乙级里的一道小题但它背后那种“把现实规则翻译成比较逻辑”的能力会在之后处理更复杂业务排序时反复派上用场。
阅读完成 · 觉得有帮助？
