PAT乙级1015德才论：多关键字排序与分类实战解析

刷到 PAT 乙级 1015 这道题的人多半是刚学完排序想找一道综合一点的题练手。德才论在乙级里属于典型的“分类 多关键字排序”题看着只有 25 分但真动手写的时候很多人会在分类条件上栽跟头或者排序优先级写反。这篇文章我会把这道题的坑一个个拆开讲清楚四类考生怎么分、比较器怎么写、第二第三关键字怎么排、代码怎么组织最后再附上我自己的 C 和 Python 两版实现并复盘几个真实报错现场帮你一次把这道题吃透。1. 先把题意吃透德才论的四类划分与筛选逻辑1.1 题面到底说了什么题目给了古代选人用人的“德”和“才”两个维度每位考生有准考证号、德分、才分三个数据。第一行读入 N、L、H 三个参数N 是考生总数L 是最低录取线H 是所谓的“高分段线”。只有德分和才分都不低于 L 的考生才有资格参与最终排序这个筛选动作是第一步也是最容易被忽略的第一步。筛选之后所有合格考生按“德才表现”分成四类。第一类是德才全尽也就是德分和才分都不低于 H第二类是德胜才德分不低于 H但才分低于 H第三类是才德兼亡但德胜才德分和才分都低于 H但德分不低于才分第四类是其他所有达到最低线的考生。这里有一个极其隐蔽的边界德分低于 H、才分却高于 H 的考生既不属于第一类德不够也不属于第二类德不够又不满足第三类才分并不低于 H所以会被划入第四类。很多人写代码时会把第四类简单理解成“德才都低于 H 且德分小于才分”一旦这样写这类考生就被漏掉了严重时会直接让排序结果多出一个人或者少一个人。输出要求也值得注意先输出合格考生人数 M再按排序规则输出每个人的准考证号、德分、才分。N 最大能到十万量级所以输入输出方式要提前想好别用太慢的读写策略。1.2 筛选、分类的顺序与边界情况实际写代码时我习惯在读入的同时完成两件事先判断是否合格不合格的直接 continue 跳过合格的立即计算类别存进 vector 或列表里。这样后面排序时就不用再关心筛选逻辑sort 只处理一份干净的数据。分类的 if 顺序必须严格按照题面来写这里我给出一个非常稳的顺序if (de H cai H) cat 1; else if (de H) cat 2; // 走到这说明 cai H else if (de cai) cat 3; // 走到这说明 de H cai H else cat 4;第二个分支不需要写“cai H”因为如果两个都大于等于 H第一个分支已经捕获了。第三个分支同样不用写“两个都低于 H”因为能走到这里说明 de 一定小于 H同时如果 cai 大于等于 H那 de 也会小于 cai肯定走不进这个分支。这个逻辑链值得反复确认它就是整道题分类部分的核心。当 L 等于 H 时也有一个特殊现象第三类条件要求两个都低于 H但合格线又要求两个都不低于 L而 L 等于 H所以第三类人数必然为 0。这种边界不一定出现在测试点里但理解清楚后你面对各种数据心里会有底。2. 排序环节拆解多关键字比较器怎么写才不会错2.1 四层优先级的直观理解排序规则可以拆成四层第一层类别小的排前面第二层类别相同看总分总分高的排前面第三层总分也相同看德分德分高的排前面第四层德分还相同看准考证号准考证号小的排前面。这个优先级本质上是一个多关键字排序问题。题目里“德才论”这个名字容易让人把注意力全放在分类上实际上分类只是预处理真正考察的是你能不能把四个层级的比较规则一次性写对。尤其是“总分降序、德分降序、考号升序”这种混合方向初学者很容易把最后一步排反。我通常在动手前先把比较规则写成一行伪代码类别升序 - 总分降序 - 德分降序 - 考号升序写清楚这一行后面不管是 C 还是 Python都是同一套逻辑的翻译。很多人一上来就写代码写到一半才发现总分相同的情况没处理再回头补就很容易漏掉“考号升序”这个条件。2.2 C 自定义比较器的写法与严格弱序C 的做法是给 sort 传一个自定义比较函数我一般写成这样bool cmp(const Student a, const Student b) { if (a.cat ! b.cat) return a.cat b.cat; 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; }这个函数里每个 if 都只在对应字段不相等时才做比较一旦分出高低立刻返回如果四个字段全部相等最后返回 a.id b.id依然是一个严格的小于关系。这里要特别注意sort 要求比较器满足严格弱序也就是同样两个元素比较器不能同时返回 true 和 true。有些同学会在某个字段写成return a.total b.total这种写法在特定编译器下可能导致排序结果错乱甚至直接段错误。我在一次测试中就见过return a.de b.de这种写法让整个程序崩溃当时排查了很久才发现是比较器破坏了等价关系。比较器的返回值逻辑可以理解成“a 是否应该排在 b 前面”。只要有一个条件能分出先后就立即返回如果走到最后让 id 来兜底就能保证任意两个元素都能分出严格顺序。这也是为什么考号必须参与排序万一前面所有字段都一样总得有个规则保证顺序确定。2.3 Python 的 key 元组技巧Python 的 sorted 和 list.sort 与 C 不太一样它不接收比较器而是接收一个 key 函数把每个元素转成一个可比较的元组。Python 元组比较时从左到右逐项比较第一个字段就能分出大小就直接结束因此很适合表达多关键字排序。关键是方向问题升序字段直接放原值降序字段需要对值取负。比如总分降序就写成-total德分降序写成-de考号升序就直接放id。一个完整的 key 可以这样构造students.sort(keylambda x: (x[cat], -x[total], -x[de], x[id]))很多人会问能不能把所有字段都放进去然后加一个reverseTrue不可以。reverse 会把所有字段的排序方向全部逆转考号也会变成降序不符合题意。所以只能手动对需要降序的字段取负。这是 Python 写法里最值得记住的一个技巧。另外如果准考证号是带前导 0 的数字比如00008存入整数会丢失前导 0输出时会变成8。所以考号字段应该使用字符串类型存储字符串在升序时按字典序比较恰好符合题目要求的“考号升序”。3. 两版完整实现与逐行要点解读3.1 C 版结构体加自定义排序先给出我认为最适合 PAT 环境的 C 写法#include cstdio #include vector #include algorithm using namespace std; struct Student { char id[10]; int de; int cai; int total; int cat; }; bool cmp(const Student a, const Student b) { if (a.cat ! b.cat) return a.cat b.cat; 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); vectorStudent stu; stu.reserve(n); for (int i 0; i n; i) { Student s; scanf(%s%d%d, s.id, s.de, s.cai); if (s.de L || s.cai L) continue; s.total s.de s.cai; if (s.de H s.cai H) s.cat 1; else if (s.de H) s.cat 2; else if (s.de s.cai) s.cat 3; else s.cat 4; stu.push_back(s); } sort(stu.begin(), stu.end(), cmp); printf(%d\n, (int)stu.size()); for (const auto s : stu) { printf(%s %d %d\n, s.id, s.de, s.cai); } return 0; }这里的几个设计点可以展开说。第一id 用char[10]配合scanf(%s)读入比 string 配合 cin 要快得多。第二continue让不合格考生直接跳过不需要为它们计算分类能省一点时间但更重要的是让后面排序数组里只有必输出的人。第三stu.reserve(n)提前分配容量避免 vector 频繁扩容带来的拷贝开销。还有一个细节排序之后直接输出stu.size()这个 size 就是我们统计出的合格人数不需要单独维护一个计数器。有些同学会额外设一个cnt变量其实完全没必要。3.2 Python 版快速读入与元组排序Python 版本要特别注意输入效率。十万行数据如果逐行调用input()即使本地能过评测环境下也可能把你卡在超时边缘。我推荐一次性读入并 splitimport sys def main(): data sys.stdin.buffer.read().split() n int(data[0]) L int(data[1]) H int(data[2]) idx 3 students [] for _ in range(n): s_id data[idx].decode() de int(data[idx 1]) cai int(data[idx 2]) idx 3 if de L or cai L: continue if de H and cai H: cat 1 elif de H: cat 2 elif de cai: cat 3 else: cat 4 students.append((cat, -(de cai), -de, s_id, de, cai)) students.sort(keylambda x: (x[0], x[1], x[2], x[3])) out [str(len(students))] for item in students: out.append(f{item[3]} {item[4]} {item[5]}) sys.stdout.write(\n.join(out)) if __name__ __main__: main()元组的前四个字段专门用来排序de和cai放在最后是为了输出时使用。如果你喜欢更清晰的代码也可以把这条元组换成一个小列表或字典但元组的空间开销更小排序也更快。data[idx].decode()是因为sys.stdin.buffer.read().split()返回的是 bytes 类型的切片转成 str 才能正常格式化输出。这里sort(keylambda x: (x[0], x[1], x[2], x[3]))中x[1] 已经是负数所以元组会自动按升序排列负数越小表示原始总分越大恰好实现了总分降序。x[2] 同理。如果读者第一次看这种写法觉得绕可以自己在纸上推两个例子很快就顺了。3.3 实现细节对照表比较项C 写法Python 写法额外比较函数定义 bool cmp 函数构造 key 元组类别升序a.cat b.catx[0]总分降序a.total b.total-total德分降序a.de b.de-de考号升序a.id b.idx[3] 原值严格弱序要求不能写 或 元组天然满足考号类型char 数组或 string字符串防止前导 0 丢失这张表对应了两种语言对“相同排序逻辑”的不同表达方式核心都是那四个优先级。我建议你在本地把两种实现都跑一遍同一份测试数据输出完全一致后才算真正理解这道题。4. 测试数据构造与常见问题排查实录4.1 一组能测穿所有排序边界的自测用例写完代码不要急着提交先自己造一组能覆盖所有分类和排序优先级的数据。下面是我常用的一组8 60 80 10001 90 85 10002 85 90 10003 70 60 10004 60 60 10005 100 60 10006 80 80 10007 55 90 10008 50 70这组数据里10007 德分 55 低于 L10008 才分 70 高于 L 但德分 50 低于 L两个人都应该被筛掉所以输出人数为 6。10001 和 10002 都是第一类但 10001 总分 17510002 总分 175总分相同时德分 90 大于 85所以 10001 排在 10002 前面。10006 总分只有 160虽然也是第一类但排在两人之后。10005 是第二类排在所有第一类之后。10003 和 10004 都是第三类10003 总分 130 大于 10004 的 120。最终顺序应该是10001、10002、10006、10005、10003、10004。把这段数据分别用两种语言跑一遍如果输出一致再看一眼考号是否都按升序处理了基本就能放心提交。我建议你也试着构造一个“德分低于 H 但才分高于 H”的考生验证一下它是不是被正确归入第四类这是整道题最容易隐藏问题的角落。4.2 我踩过的 5 个坑第一个坑是第四类判定写得太狭隘。我最初把第四类写成“德才都低于 H 且德分小于才分”结果像前面说过的那样把德分低于 H、才分高于 H 的考生漏掉了。提交后有一个测试点怎么都对不上最后打印出所有考生的分类明细才定位到问题。第二个坑是比较器里用了。某个版本我为了省代码写成return a.de b.de本地小数据测试一切正常但数据量一大就出现排序错乱甚至有一次直接崩了。原因是sort要求严格弱序相等元素必须返回 false一旦相等也返回 true等价关系就破坏了后续操作就会进入未定义状态。第三个坑是准考证号用 int 存。题目样例里的考号恰好没有前导 0但评测数据里可能会出现一旦用 int 读入前导 0 就没了输出格式错误不说排序时“考号升序”也没法保证。后来我统一用字符串存问题立刻消失。第四个坑是 Python 里试图用reverseTrue解决降序。我见过不止一个人把元组写成(cat, total, de, id)然后reverseTrue结果不仅总分变成降序连考号也变成降序完全偏离题意。记住多字段排序里混合方向必须用负数技巧不要依赖 reverse。第五个坑是 M0 的输出格式。如果所有考生都不合格输出应该是单独一行0后面不再跟任何考生数据。有些实现里如果输出逻辑写到一半 break可能导致连 0 都不输出测试点直接报错。我习惯先拼好输出列表再统一写入这样天然避免这类问题。4.3 性能与读写习惯C 混用scanf和cout时如果不同步会导致输入输出顺序异常。稳妥的做法是要么全用scanfprintf要么在main开头加上ios::sync_with_stdio(false); cin.tie(0);后全用cincout。我自己习惯用scanfprintf因为这类题输入量大printf 的格式化控制更直接。Python 侧的核心建议只有一条不要逐行input()。十万行数据逐行读入不是不行但耗时明显高于sys.stdin.buffer.read().split()。输出也尽量拼成一个大字符串一次性写出避免十万次print调用。我在本地对比过同一个程序只改输入方式耗时差出好几倍。还有一个容易忽略的点结构体数组排序时sort 内部会发生大量元素拷贝。如果结构体里有 string 或复杂对象拷贝成本会上升但这里的 Student 只有几个 int 加一个 char 数组拷贝成本很低不用担心。想更激进地避免拷贝可以改成 vector 存储 index 后对 index 排序但对这道题来说完全没有必要。5. 从德才论提炼出的通用排序套路5.1 多关键字排序的模板化思考做完了德才论你会发现自己其实掌握了一套可复用的流程先把每个元素应有的排序字段算好再统一交给排序函数。无论题目是学生成绩排名、比赛积分榜还是某种结构体的多属性排序思路都一样。我习惯把这套流程固定成三个步骤。第一步确定“参与排序的元素”是谁把不需要进入排序的成员在预处理阶段就剔除。第二步找出所有参与排序的字段并对每个字段标注方向升序还是降序。第三步根据自己的语言选择合适的表达方式C 写cmpPython 写key元组然后和标准输出格式做一次本地验证。这道题里“分类”本身也是一个字段这是它比一般排序题多出来的变化。以后你遇到带分组的排序比如按学校排名再按总分排名完全可以把“组别”“类别”当成排序字段优先放在元组第一位。这种抽象能力比记住某一道题的具体条件更重要。5.2 个人经验与复盘我第一次写 1015 时状态非常典型样例会过提交就挂。后来发现是我把第四类的判定写窄了漏掉了“德低于 H、才高于 H”的那类人。那次经历让我养成一个习惯凡是带“其他”分类的问题写代码前先列出所有真假组合逐个确认它落在哪个分支。这个方法救了我很多次。另一个习惯是分类结果一定要在 push 进数组之前算好别把 cat 字段留空或默认成 0。之前有一次我把 cat 定义成结构体最后一个成员读取时忘了赋值排序结果看起来完全随机。后来我再写这类题目时都会在一个地方完成“筛选 分类 入组”不让任何一个中间状态流到排序阶段。如果你正卡在这道题上不妨先放下代码拿一张草稿纸把四类考生和四个排序条件画一遍再把上面那组测试数据手算一遍。这个过程走通之后代码基本就是水到渠成的事。这道题的难点从来不是语法而是分类和排序规则的严谨程度。把严谨性练出来你收获的远远不止 25 分。