企业官网建设流程全解析

[PAT 乙级] 1015 德才论 (25 分)——(排序)

这道题我印象挺深的。刚刷PAT乙级那阵子，做到快结尾的时候碰到它，第一眼看过去觉得题目很长，还拽了个"德才论"的文言文背景，心里有点发怵。真正动手做下来才发现，它其实就是一个典型的排序应用题，考的无非三件事：读懂分级规则、把结构体定义好、写对自定义排序比较函数。很多同学卡在这道题上，不是不会排序，而是栽在分类优先级和比较函数那几行逻辑里。这篇博客我把自己从读题到AC的全过程理一遍，顺便把踩过的坑和调试心得都倒出来，给正在刷PAT乙级的朋友做个参考。

这道题不会涉及什么高深算法，本质是排序，但要把分数完整拿下来，得注意几个容易丢分的小细节。适合刚学完sort排序、想做点综合应用来练手的人，也适合准备参加计算机水平考试的同学拿来检测自己结构体和自定义比较函数有没有学扎实。

1. 题目到底在讲什么——先读懂古代选人标准

1.1 规规矩矩把题目拆开看

题目借用了古代关于德才的讨论。给定一批考生的准考证号、德分、才分，再给两条线：最低录取线L和优先录取线H。德分和才分都达到H的，是"德才全尽"，也就是第一等；德分达到H但才分没达到H的，是"德胜才"，第二等；德分和才分都没达到H，但德分不低于才分的，是"才德兼亡但德分比才分高"的人，第三等；剩下的只要过了L线，排第四等；没过L线的，直接淘汰，不参与输出。

说实话，这四等划分本身不算难，难的是很多人把第三等给理解偏了。代码里会看到一堆人写"德分大于等于才分就进第三等"，其实不对，还要先确保德分跟才分都小于H，且都大于等于L。换句话说，这个第三等是"两条线都不够H，但德还行"的那批人。如果德分大于等于H，才分小于H，那是第二等，不是第三等。这个前提一旦搞混，排序结构全乱。

1.2 数据规模决定了你该怎么写

题目给的N最大是十万。这个数据量用O(nlogn)的排序完全没问题，sort函数稳稳接住。但如果有人在这个地方非要手写冒泡排序，那就麻烦了，十万个元素冒泡是过不去的。所以这道题实际上还有个隐性的提醒：会估数据规模，知道上什么排序算法。

另外，我习惯于把准考证号当作整数来读，而不是字符串。因为题目保证它是6位正整数，直接存成int就行。输出的时候也不用来回处理前导零问题，因为输入的数字就是让你原样输出的，整数格式直接打出来不会有问题。

2. 分类和排序规则的优先级——这是全题最值钱的部分

2.1 五类人是怎么被排出来的

我们可以给每个考生算一个等级，等级越小越靠前。第一等给1，第二等给2，第三等给3，第四等给4，淘汰的直接给一个很大的数比如5。然后排序的时候先按等级排，等级相同再看总分，总分相同再看德分，德分还相同才按准考证号排。

我当时第一版代码是直接写了四个if，把前四等的人往vector里塞，第五等过滤掉。这样也行，但后面会有一个麻烦：第一等和第二等、第三等和第四等之间的先后关系，如果不小心写错，输出顺序就错了。

更稳的办法是结构体里加一个category字段，读入的时候就把每个考生划到具体的类别里，最后一并排序。这个思路我觉得比"边读边塞四个向量"更清晰，调试的时候一目了然。下面是我用的划分逻辑：

if (de < L || cai < L) type = 5; else if (de >= H && cai >= H) type = 1; else if (de >= H && cai < H) type = 2; else if (de < H && cai < H && de >= cai) type = 3; else type = 4;

这段判断顺序其实是精心设计的。先淘汰，再分第一等，再分第二等，再分第三等，最后兜底第四等。因为每个if之间是互斥的，所以顺序影响不大，但先做淘汰会让后面的逻辑更干净，避免后面每个if都带着L/H边界判断。

2.2 排序规则的三级联动

题目要求的排序规则是：类别升序，总分降序，德分降序，准考证号升序。总分相同的情况很常见，所以必须在自定义比较器里把总分比较放最前面，然后依次是德分、考号。千万不要只写一个总分降序就交差，那样样例会挂得很惨。

我也见过有人把总分的逻辑写进结构体，搞一个重载运算符或者lambda捕获，但比较器里最容易犯的错，是忽略了"总分相同再比德分"这一点。很多人在总分不同的情况下直接按总分排序，总分相同又不做任何处理，sort的结果当然不稳定，最后输出顺序跟着随机。

还有一个细节是第三等和第四等内部也要遵循同样的排序规则，不要以为分类定了就完事。换句话说，所有输出的人放在一个大池子里统一排序也行，不用每个类别单独排。只要类别字段本身参与比较，类别之间自然就分开了。

3. 结构体定义与sort比较器的实现细节

3.1 结构体的字段设计

结构体字段我建议这么写：

struct Student { int id; int de; int cai; int type; int sum; };

id是准考证号，de和cai是德分才分，type是1到5的类别，sum是总分。你可能会问，sum难道不能在比较器里头现算吗？其实也可以，比如a.de + a.cai每次比较都算一遍。但排序过程有大约n log n次比较，每次都调用加法，虽然代价不大，不如读入时顺手把sum算好存进去，清晰又高效。

读入的时候一行一行读：

int n, L, H; scanf("%d%d%d", &n, &L, &H); vector<Student> v; for (int i = 0; i < n; i++) { Student s; scanf("%d%d%d", &s.id, &s.de, &s.cai); s.sum = s.de + s.cai; // 然后根据 de, cai, L, H 给 s.type 赋值 if (s.type != 5) v.push_back(s); }

注意：这里只把type不等于5的push进去，也就是淘汰的人直接过滤，后面的排序和输出都不用再关心，省心。

3.2 自定义比较器该怎么写才算完整

C++的sort配合自定义比较函数，是这道题最核心的考点。我放一个完整的比较器出来：

bool cmp(const Student& a, const Student& b) { if (a.type != b.type) return a.type < b.type; if (a.sum != b.sum) return a.sum > b.sum; if (a.de != b.de) return a.de > b.de; return a.id < b.id; }

这四行逻辑顺序就是题目的字面意思，一条都不能少。很多人写到最后就忘了那行return a.id < b.id，最后考号大的反而排前面。考号是6位数，按升序排，等于说编号越小的越先输出。

如果你用的是C++11以后的版本，也可以用lambda这样写：

sort(v.begin(), v.end(), [](const Student& a, const Student& b){ if (a.type != b.type) return a.type < b.type; if (a.sum != b.sum) return a.sum > b.sum; if (a.de != b.de) return a.de > b.de; return a.id < b.id; });

lambda写起来更紧凑，尤其适合题目做完还想再本地跑几个测试用例的情况。个人觉得熟了以后lambda更顺手，因为不用把比较函数单独拎到外面去，读代码的时候逻辑更聚拢。

3.3 关于手写快排的选型思考

我在中文社区里看到不少人纠结要不要手写快排，其实没必要。sort已经是优化过的混合排序，十万级别数据下性能绰绰有余。真正需要注意的反而是：sort要求比较器是严格弱序的，如果两个学生各项指标都一样，返回a.id < b.id是可以的，但如果你返回的是a <= b这种，可能触发未定义行为，在部分编译器上会崩或者排序结果诡异。

手写快速排序在这道题里纯属给自己增加负担。除非你是在练习手写排序算法本身，否则PAT这种比赛环境下，谁稳谁快就用谁。sort的稳定性虽然不如stable_sort，但我们这里比较器已经把全部顺序条件都写全了，不存在需要"保住原始顺序"的场景，所以sort完全够。

4. 完整提交代码与每个关键变量的妙用

4.1 一份可以直接提交的C++代码

直接给一份完整可运行的版本，用的是scanf/printf，因为题目数据量到十万，cin/cout如果没关同步，也可能超时，干脆用C风格的输入输出省得折腾。

#include <cstdio> #include <vector> #include <algorithm> using namespace std; struct Student { int id, de, cai, type, sum; }; bool cmp(const Student& a, const Student& b) { if (a.type != b.type) return a.type < b.type; if (a.sum != b.sum) return a.sum > b.sum; 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); vector<Student> v; v.reserve(n); for (int i = 0; i < n; i++) { Student s; scanf("%d%d%d", &s.id, &s.de, &s.cai); s.sum = s.de + s.cai; if (s.de < L || s.cai < L) { s.type = 5; } else if (s.de >= H && s.cai >= H) { s.type = 1; } else if (s.de >= H) { s.type = 2; } else if (s.de >= s.cai) { s.type = 3; } else { s.type = 4; } if (s.type != 5) v.push_back(s); } sort(v.begin(), v.end(), cmp); printf("%zu\n", v.size()); for (int i = 0; i < (int)v.size(); i++) { printf("%d %d %d\n", v[i].id, v[i].de, v[i].cai); } return 0; }

注意看这里的分类判断，我把else if (s.de >= H && s.cai < H)简化成了else if (s.de >= H)。因为前面的if已经排除掉"德分和才分都大于等于H"的情况，所以能走到这一步并且德分还大于等于H的，必然满足才分小于H。这个化简可以减少代码噪音，但前提是你心里非常清楚前面的分支已经把情况过滤完了。如果你自己容易绕晕，建议还是老老实实把全部条件写全。

4.2 分类判断里藏着的一个陷阱

很多第一次写的同学，第二类和第三类判断经常写反。原因是他们直接去记"德胜才"是德分高，"才德兼亡"是德分低，然后看到第二类"德分大于等于H、才分小于H"就以为第二类优先级一定在所有"德分低于H"的第三类之前。这个想法本身没错，但落到代码里，如果第三类的条件写成else if (s.de < H && s.cai < H && s.de >= s.cai)，且这个if放在第二类之前，那么第二类的人会被第三类拦截吗？

不会。因为第二类是德分大于等于H，第三类第一个条件是德分小于H，两者条件互斥。可问题在于：如果第二类的if条件漏写了"才分小于H"，比如直接写else if (s.de >= H)，那它确实能覆盖第二类，但一旦这个分支在判断顺序上放在了"德分和才分都大于等于H"的后边，就万事大吉。但如果第一类判断写成了else if (s.de >= H || s.cai >= H)，逻辑就彻底乱了，第一类会吞掉一大批第二类、第三类的人。

这是我调试时踩过最深的坑。所以建议在划分完类别后先打印一遍所有人的type，核对边界样例再排序输出。

4.3 时间复杂度与空间复杂度的快速估算

假设n是十万，sort排序复杂度是O(nlogn)，大约十万乘以十七，一百七十万次比较，现代CPU跑起来微秒级到毫秒级。加上读入输出也就O(n)，整体非常轻。空间上vector最多存十万人，每个Student是5个int，大约20字节，乘以十万是2MB左右，完全没压力。

这题的时间限制通常是200ms左右，其实是比较宽松的。但如果有人用cin/cout而且没加ios::sync_with_stdio(false)，十万条输出加上排序，可能就会压线甚至超时。我在本地用cin/cout测过，关不关同步差距挺大的，尤其是PAT的老版评测环境，C风格IO肯定更稳。

5. 常见错误与调试记录——这些坑我全都踩过

5.1 问题速查表

我把这道题最常见的几种错误整理成了表格，按出现频率排了个序：

这六条里，最隐蔽的是第二条和第四条。第二条隐蔽是因为它不是编译错误，也不是运行错误，纯粹就是输出多了一行，跟标准答案一比就会被发现，但很多人对着屏幕看半天看不出毛病。第四条则是因为字符串字典序和数字序在样例规模较小时可能一致，一旦有跨位数的考号就会露馅。

5.2 一份快速的边界测试模板

如果你想在本地快速验证自己代码对不对，可以构造几组特殊的输入。我先分享一组最简单的：

5 60 90 100001 90 90 100002 90 60 100003 80 80 100004 60 60 100005 50 50

这里H=90，L=60。第一人德才双高，type=1；第二人德够才不够，type=2；第三人德才都低于90但德分等于才分，type=3；第四人刚过线，type=4；第五人才分只有50，淘汰。输出顺序应该是100001、100002、100003、100004，淘汰的不输出。

多测几组这种"每个类别各一个"的用例，基本能把分类逻辑覆盖住。还有一类测试重点是总分相同：比如两个type相同的人，一个德分高但才分低，一个总分一样但德分低，排序应该德分高的在前。这个边界特别容易挂，建议单独构造。

5.3 关于读题的一个个人体会

这道题原文描述里有个细节，第三等那句是"德分不低于才分"，注意是"不低于"，不是"高于"。我刚开始下意识理解成"德分大于才分"，结果把德分等于才分的人全都归到第四等去了，输出跟标准答案差得很远。这种一字之差在算法题里非常致命，读题时必须抠字眼，尤其遇到带中文背景的题。

另外，题目说L是"最低录取分数线"，H是"优先录取线"，这个优先录取线跟"优秀"不是一个概念。只要德分和才分都达到H，就是第一等，没有额外的"超过H多少分"的说法。所以德分90、才分91和德分100、才分100在第一类里地位一样，后面排序就看总分和德分了。

6. 这道题能带给你的收获不止于排序

6.1 从"会排序"到"会应用"的跨越

很多初学者刷排序题时只练sort怎么调用，但PAT乙级给人感觉比较舒服的一点是，它经常把数据结构、排序和一些实际背景揉在一起。做完这道题，你会意识到排序不只是"把数字排个序"，而是"给定一个自定义的客观标准，把一批记录排出合理顺序"。

以后碰到更复杂的场景，比如按多个字段排序、按枚举类型排序、甚至按两个字段的某种组合排序，思路都是一样的：先定义结构体，再写比较器，最后sort。这种能力在实际工作里太常用了，比如按员工的部门和绩效排序，按订单的优先级和时间排序，都是同一套模式。

6.2 如何把这题的思路迁移到别的题目

我做完这道题后又去做了类似的多关键字排序题，比如按分数排名、按名字字典序加成绩排序等，明显轻松很多。核心方法就是：把"比较规则"从主逻辑里抽出来，放到比较器里。一旦比较器的思路清晰，主流程几乎不用改，只是改一改比较器的几行返回语句。

另外，这道题也让我养成了一个习惯：凡是结构体排序，一律在结构体里定义好所有参与排序的字段，而不在比较器里临时算。比如总分，如果不存，每次比较都要加一遍，费时且容易在比较器里写错变量名。

6.3 给刚开始刷PAT乙级同学的一点建议

乙级题目总体是在考察基础功，但1015这道题能把很多人卡住，原因不是难，而是"繁琐"。读题要读两遍，条件要分类讨论，排序规则要逐条实现。我建议不要一上来就写代码，先拿张纸把四种人的判定条件和排序规则写清楚，再动键盘。这样即便中途debug，思路也不会乱。

调试的时候，可以加一行临时的遍历打印，看看每个考生的type到底是什么。我当时就是靠这个找到分类错误的。也别怕多用printf做临时输出，这些调试代码最后不删也不会影响提交，只是洁癖的人可能会删掉。

7. 我最后想多聊两句的地方

这道题的背景名"德才论"本来是说一个人要德才兼备，但它真正刻进我记忆里的不是文言文，而是那个排序条件的一整个串联逻辑。刷题多了你会发现，读题花的时间往往比写代码花的时间多，尤其是这种带了一堆限制条件的模拟型题目。

我个人做这种题的节奏是：先花五分钟搭框架，确认结构体字段和基本输出逻辑，再花十分钟把条件判断和排序规则仔仔细细写对。宁可慢一点，也不要写完再大改。每次看到有人在论坛上问"为什么我这题老是错"，我第一反应都是让他先把分类打印出来看看，而不是急着查排序函数有没有写错。

如果后续你还想练类似的套路，可以找找带有"类别+分数+编号"三关键字排序的题目多刷两遍。刷熟之后，再看到需要把复杂比较规则塞进sort的题，基本就能一眼看穿出题人想要你干什么了。