刷到 PAT 乙级 1015“德才论”的时候我正在集中刷结构体和排序相关的题目。说实话这题的故事背景挺有意思——古人把人才分成“才德全尽”“德胜才”“才德兼亡尚有德”几类放在现代算法题里本质上就是给你 10 万个考生的德分和才分再给两条分数线 L 和 H让你按规则分类、排序、输出。考点非常集中结构体、多关键字排序、条件分支判类外加一点输入输出的基本功。这题适合谁刷备考 PAT 乙级的同学必须刷它是乙级排序题里的经典代表刚学完结构体和 qsort 的 C 语言初学者也适合拿来练手。它不像有些题上来就“卡壳”在数据范围上而是把逻辑基本功和代码基本功都考了一遍。我做完之后最大的感受是这道题不难但很考验你的逻辑梳理能力——分类规则排得不明不白compare 函数写出来就大概率是错的。1. 刷题之前先弄懂这道“德才论”到底在考什么1.1 题目讲了个什么故事这道题借用了中国古代“德才论”的人才分类思想。司马光在《资治通鉴》里评论过“才者德之资也德者才之帅也”意思是一个人光有才不行还得有德。题目抓住这个点把每个考生拆成两个分数德分de和才分cai。输入给出三个整数 N、L、H其中 N 是考生总数L 是“最低录取线”H 是“优先录取线”也就是高分段。考试规则是德分和才分都达到 L 才有资格被录取达不到的考生直接落榜连排队的资格都没有。具体输出要求我记得很清楚先输出达线人数 M然后按类别优先级从高到低输出每个人的准考证号、德分、才分。这道题如果只看文字描述大家基本都能读懂但做起来容易踩坑的地方恰恰藏在分类条件和排序细节里。我后面会重点展开。1.2 核心考点拆解我把考点拆成四块也是 PAT 这类题目最经典的套路结构体每个考生有准考证号、德分、才分、总分、类别标签这么多字段用结构体一次装下比定义一堆平行数组可读性强得多。分类逻辑根据 L 和 H 把达线的考生分成四类本质是一组互斥的 if-else 分支。多关键字排序类别优先级、总分降序、德分降序、准考证号升序四个关键字按顺序比较。输入输出数据量到 10 万级别时用没用对输入输出函数会影响实际运行时间。这四块单独拿出来都不难但合在一起就考验你的代码组织能力了。我见过不少同学栽在“分类规则似乎写完了但排序结果总有一部分不对”的尴尬局面上原因基本都是对“互斥分支”和“排序优先级”的理解不到位。1.3 适合谁刷、刷完能收获什么如果你是跟着翁恺老师的 C 语言课程在学刚学完结构体和 qsort那这道题几乎是量身定做的练习题。它的知识点完全落在课程范围内但综合度比课本习题高一个台阶。刷完之后结构体的使用、二维排序、条件判类这些基本功都会扎实很多。如果你是在准备 PAT 乙级考试这道题更得练。乙级排序题非常多1015 这种带分类的算是“排序业务逻辑”的复合题。做会这一题后面再遇到类似的“先分类、再排序”的题比如 1037 在霍格沃茨找零钱那种考试场景题你就知道套路了。2. 解题思路拆解把古人的分类规则翻译成代码2.1 先弄明白两条分数线的作用L 和 H 这两个数字是整个逻辑的关键。简单说L 是“能否参与排名”的门槛H 是“能否进入更高类别”的分界线。第一层判断发生在读入环节只要德分或者才分有一个低于 L直接扔掉。这一步很关键它决定了你后面存进数组的人都是“有资格被考虑录取”的。第二层判断是对达线的人打类别标签这个时候 H 才派上用场。所以永远不要把 L 和 H 混在一个公式里它们是两个维度的事。注意第一层判断时只要有一门低于 L 就丢弃不是“两者之和低于某个值”。德才兼备的录取规则里单科不过线直接淘汰这点和某些只看总分的高考录取思路不一样。2.2 四类考生的互斥分类达线之后按德分和才分与 H 的关系原题把考生分成四类类别名称条件第一类才德全尽德 H 且 才 H第二类德胜才德 H 且 才 H第三类才德兼亡尚有德德 H 且 才 H 且 德 才第四类其余达线者满足第一、二、三类以外的达线者这里有一个特别容易出错的地方第三类的判断条件里“德 H 且 才 H”和“德 才”是同时成立的不少人会把“德 才”里的等号丢掉。如果德等于才两个人的德才都低于 H按题意他们俩在德行上算“一样好”应该归入第三类。丢掉等号会把这类人漏到第四类去输出顺序就错了。另一个容易出错的地方在第四类。第四类不是某个具体条件的集合而是一个兜底分支——只要不满足前三类且德才都达了 L就是第四类。写成代码时直接用 else 兜底最稳不要去显式枚举第四类的各种边界组合比如“德 H 且 才 H”、“德 H 且 才 H 且 德 才”枚举容易漏。2.3 排序规则拆解四个关键字按优先级排分类只是第一步同一类别里的排序规则才是代码里真正的重头戏总分德 才高的排前面总分相同德分高的排前面总分和德分都相同准考证号小的排前面不同类别之间类别编号小的排前面其实把“类别”当成最优先的关键字整个排序就统一成了一次四关键字排序。我在比较器里就是把类别优先级放在最外层让先分类再排序这步变得非常自然。注意输出准考证号时原题保证准考证号是正整数直接用 int 存即可。但如果将来遇到带前导零的编号就得上零填充的格式化输出或字符串这是题外话但值得记一笔。3. 完整实现C 语言从思路到 AC 的代码3.1 数据结构结构体里放什么我的第一版代码结构体是这样设计的typedef struct { int id; // 准考证号 int de; // 德分 int cai; // 才分 int total; // 总分 de cai int cls; // 类别1~4 } Student;total 这个字段其实是多余的——每次比较时现算 de cai 也行。但我强烈建议存进结构体而且是在读入的时候就顺手算好。原因有两个一是代码更短更清晰比较器不用反复做加法二是总分在排序里被反复比较预计算能省掉若干次微不足道的 CPU 时间虽然这道题数据量不大无所谓但养成好习惯没有坏处。数组大小方面N 最大能给到 10 万我习惯直接开Student students[100010]比 N 上限多开一点心里踏实。3.2 判类与入库边读入边分类这部分我建议直接写在读入循环里或者单独提一个判类函数也行。核心代码如下if (de l || cai l) { continue; // 德分或才分低于 L直接淘汰 } Student s; s.id id; s.de de; s.cai cai; s.total de cai; if (de h cai h) { s.cls 1; } else if (de h) { s.cls 2; } else if (cai h de cai) { s.cls 3; } else { s.cls 4; } students[m] s;这里我特别想解释为什么第三类判断写cai h de cai。当代码走到这个分支时前面的de h cai h已经失败而且de h也失败了所以此时德分一定小于 H。这时代码里只需要关心才分是否小于 H以及德分是不是不低于才分——也就是cai h de cai。这就是“前面分支已经帮你排除掉一部分条件”的典型例子充分理解这一点你的分类代码就不会写得又臭又长。3.3 qsort 比较器的正确写法C 语言里排序最顺手的就是qsort。它的第四个参数是函数指针签名长这样int compare(const void *a, const void *b)比较器内部要先强制转换成结构体指针。返回值是负数代表 a 排前面正数代表 b 排前面0 代表两个元素相等。关键规则是你要实现“a 想要排在 b 前面就返回负数”。这道题的比较器我是这么写的int compare(const void *a, const void *b) { const Student *x (const Student *)a; const Student *y (const Student *)b; if (x-cls ! y-cls) { return x-cls - y-cls; // 类别小的排前面 } if (x-total ! y-total) { return y-total - x-total; // 总分高的排前面 } if (x-de ! y-de) { return y-de - x-de; // 德分高的排前面 } return x-id - y-id; // 准考证号小的排前面 }我当初在写比较器的时候翻过一次车第一次写成了return x-total - y-total结果总分低的反倒排前面了。后来想明白了——降序要用y - x升序才是x - y。这个方向问题非常隐蔽因为代码编译不会报错只有对着样例数据逐条核对才能发现。关于比较器里直接做减法这道题的分数范围很小德才都是 0~100 的整数总分 0~200所以相减不会溢出直接写没有问题。但如果在分数范围很大或者数值可能接近 INT_MAX 的场景稳妥的做法是返回(x y) ? -1 : (x y) ? 1 : 0这种显式比较结果避免减法溢出。顺便说一句如果你用 C 写这题直接用sort也一样顺手比较器的写法思路完全不变只是把函数指针换成函数对象或者 lambda 表达式。PAT 乙级对 C 和 C 都收关键是排序逻辑本身要对。3.4 完整代码参考把上面这些拼起来就是一份能直接跑过的完整代码。我贴出来供你参考#include stdio.h #include stdlib.h typedef struct { int id; int de; int cai; int total; int cls; } Student; Student students[100010]; int m 0; int compare(const void *a, const void *b) { const Student *x (const Student *)a; const Student *y (const Student *)b; if (x-cls ! y-cls) return x-cls - y-cls; if (x-total ! y-total) return y-total - x-total; if (x-de ! y-de) return y-de - x-de; return x-id - y-id; } int main() { int n, l, h; scanf(%d%d%d, n, l, h); for (int i 0; i n; i) { int id, de, cai; scanf(%d%d%d, id, de, cai); if (de l || cai l) continue; Student s; s.id id; s.de de; s.cai cai; s.total de cai; if (de h cai h) { s.cls 1; } else if (de h) { s.cls 2; } else if (cai h de cai) { s.cls 3; } else { s.cls 4; } students[m] s; } qsort(students, m, sizeof(Student), compare); printf(%d\n, m); for (int i 0; i m; i) { printf(%d %d %d\n, students[i].id, students[i].de, students[i].cai); } return 0; }这段代码结构很清晰适合反复对照。你可以先不看代码自己写一遍写不出来再看答案对照这样记忆更深刻。4. 踩坑实录那些“题会做但 A 不了”的细节4.1 输入输出的性能陷阱PAT 的很多题目数据量一上来cin /cout 就会拖慢速度。这道题 N 最大 10 万其实不算特别大但如果你在 PAT 的旧版编译环境里混用cin和printf或者不关流同步偶尔会触碰到时间限制的边界。我在做这道题的时候用的全是scanf/printf这也是 C 语言选手最稳妥的选择。如果你非要用 C 的cin/cout记得在main开头写上ios::sync_with_stdio(false); cin.tie(0);不然 10 万数据的读入写出一旦超时你甚至不知道自己是败给逻辑还是败给 I/O。这个坑我在早期刷题时踩过好几次后来直接养成了“高频 I/O 一律 scanf/printf”的习惯。4.2 比较器里的隐藏逻辑问题比较器最简单的错误有三种方向写反、相等时没返回 0、直接相减溢出。这道题的方向错误我在前面已经讲过了。关于“相等时没返回 0”我解释一下为什么它会出问题qsort 要求比较器满足严格弱排序如果两个考生所有字段都相同比较器必须返回 0否则在数据量大的时候可能出现结果不稳定甚至越界访问。虽然这道题里准考证号是唯一的理论上不会出现完全相同的人但写比较器时还是要有这个意识。还有一个细节比较器的顺序判断里我用的是“先判断 cls再判断 total再判断 de最后才判断 id”。这个顺序就是排序优先级写反了哪怕一个字段最后排列出来的结果就完全不符合题意。比较器里的每一行都要仔细对照原题规则宁可多读两遍题也别急着提交。4.3 分类逻辑上的三个高频错点我总结了身边同学在这道题上最容易犯的三个错误列成表给你对照高频错点错误表现正确做法第三类漏了等号德 才的情况被归到第四类写成de cai必须带等号第四类显式枚举分支漏掉“德 H 且 才 H”的组合用 else 直接兜底读入时不筛达线考生数组里混着落榜考生输出数量错读入时先判断de l || cai l就 continue特别是第一个错点几乎每个没 AC 的人都踩过。德分等于才分时古人眼里这两个人德行相当都属于“才德兼亡尚有德”那一档。等号一漏这些考生就掉进第四类输出的顺序和题目的期望完全错开。4.4 边界数据自测法刷题时养成的另一个习惯是写完代码先自测几组边界数据再提交。比如5 60 80 1001 60 60 1002 80 60 1003 80 80 1004 60 80 1005 59 99这组数据里1005 的才分虽然很高但德分低于 L 线直接被淘汰。1001 德才都刚过 60归第四类。1002 德分达 H 才分未达 H归第二类。1003 德才都达 H归第一类。1004 德分未达 H、才分达 H归第四类。你拿这样的数据对着代码跑一遍分类和排序逻辑对不对立刻见分晓。我自己的测试习惯是每条边界条件都要单独构造一条数据比如刚好等于 L、刚好等于 H、等于 H 差 1 这些位置确保每一行分支都被走到。像这道题H 等于 L 时也要测一下。这时第二类、第三类理论上不会有人整体退化成“按总分德分排序”的普通排序题能帮你验证读入过滤逻辑和排序比较器没写串行。5. 这类题的通法多关键字排序的心法5.1 多关键字排序的通用写法多关键字排序在编程题里太常见了——先按主关键字排主关键字相同再按次关键字排以此类推。通法就是一层一层的if判断逐级深入每一层只处理一个关键字直到最后一个关键字为止。if (a-key1 ! b-key1) { return 按 key1 的规则比较; } if (a-key2 ! b-key2) { return 按 key2 的规则比较; } // ... return 按最后一个 key 的规则比较;这个结构本质上是一个“字典序”比较。我把这类题的套路总结成一句话从第一优先级的关键字开始往下写每个关键字只在一层 if 里出现最后一个关键字不用 if 包裹也安全——因为走到最后说明前面的关键字都相等了。这道题的四关键字排序就是把这个通法用了四层。你只要把“优先级”理解清楚写成代码就是顺手的事。5.2 从 PAT 1015 到日常开发多关键字排序不只是考试里的技巧。举个最日常的例子你在数据库里执行ORDER BY cls, total DESC, de DESC, id ASC服务器底层做的其实和 qsort 比较器是同一件事——按照指定优先级逐字段比较、合并排序结果。所以你要是能把这道题里的比较器写得又快又准将来写业务代码时对排序逻辑的感知力也会不一样。另外这种“先分类、再排序、最后按序输出”的三段式结构其实对应了很多现实场景。比如招聘系统的候选人筛选先按“是否满足硬性条件”过滤再按“综合评分”排序再比如电商商品列表先按“上架状态”过滤再按“销量、评分、价格”排序。逻辑模型完全一致只是在 PAT 里你是用结构体和 qsort 实现的而已。6. 考完之后再看一眼这道题教会我的几件事6.1 从翻车到 AC 的一次复盘这道题做完全程我最大的体会不是“我会结构体排序了”而是“把需求翻译成代码时要先理清优先级再动手写”。我一开始动手太快边写边想分类规则结果比较器写出来时脑子里一团浆糊提交后总有几个测试点过不去。后来强迫自己先在草稿纸上把四类人才的条件和排序四个关键字列成表再动键盘十几分钟就 AC 了。现在遇到任何带复杂排序的题我都习惯先画表、再写代码效率高很多。6.2 顺着 1015 再往前刷两步如果你刷到这道题的同时还在往前推进 PAT 乙级的其他题目建议把同类型的“结构体排序 条件分类”题放在一起集中刷。比如 1037 在霍格沃茨找零钱那种场景化题目虽然考点不一样但都能训练你把自然语言描述快速转成条件判断的能力。刷够十道这种题之后再见这类题基本就不慌了。最后分享一个小技巧提交前把上面那个自测数据跑一遍再用printf(%d\n, m)先看看达线人数对不对。人数错了分类必然有问题人数对了问题大概率在比较器。这个排查顺序帮我省下过不少时间希望对你有用。