[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); vectorStudent 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位数按升序排等于说编号越小的越先输出。如果你用的是C11以后的版本也可以用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); vectorStudent 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 问题速查表我把这道题最常见的几种错误整理成了表格按出现频率排了个序错误类型具体表现原因解决办法分类条件写错第二类和第三类顺序反了输出顺序全乱对德才两条线的组合关系没理清先画一张真值表再写if分支忘了过滤第五类输出行数明显比标答多淘汰的人也被push进vector在push前检查type!5排序字段顺序不对总分相同的情况下德分乱序比较器少写了德分比较按类别、总分、德分、考号依次比较准考证号按字符串处理排序结果和预期差很远用了字典序而不是数字序用int存考号比较时按数值大小输入输出没加速本地很快提交超时cin/cout同步开销大用scanf/printf或关同步输出人数统计错总数少了一个或两个打印的是n而不是v.size()用v.size()统计人数这六条里最隐蔽的是第二条和第四条。第二条隐蔽是因为它不是编译错误也不是运行错误纯粹就是输出多了一行跟标准答案一比就会被发现但很多人对着屏幕看半天看不出毛病。第四条则是因为字符串字典序和数字序在样例规模较小时可能一致一旦有跨位数的考号就会露馅。5.2 一份快速的边界测试模板如果你想在本地快速验证自己代码对不对可以构造几组特殊的输入。我先分享一组最简单的5 60 90 100001 90 90 100002 90 60 100003 80 80 100004 60 60 100005 50 50这里H90L60。第一人德才双高type1第二人德够才不够type2第三人德才都低于90但德分等于才分type3第四人刚过线type4第五人才分只有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的题基本就能一眼看穿出题人想要你干什么了。
[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); vectorStudent 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位数按升序排等于说编号越小的越先输出。如果你用的是C11以后的版本也可以用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); vectorStudent 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 问题速查表我把这道题最常见的几种错误整理成了表格按出现频率排了个序错误类型具体表现原因解决办法分类条件写错第二类和第三类顺序反了输出顺序全乱对德才两条线的组合关系没理清先画一张真值表再写if分支忘了过滤第五类输出行数明显比标答多淘汰的人也被push进vector在push前检查type!5排序字段顺序不对总分相同的情况下德分乱序比较器少写了德分比较按类别、总分、德分、考号依次比较准考证号按字符串处理排序结果和预期差很远用了字典序而不是数字序用int存考号比较时按数值大小输入输出没加速本地很快提交超时cin/cout同步开销大用scanf/printf或关同步输出人数统计错总数少了一个或两个打印的是n而不是v.size()用v.size()统计人数这六条里最隐蔽的是第二条和第四条。第二条隐蔽是因为它不是编译错误也不是运行错误纯粹就是输出多了一行跟标准答案一比就会被发现但很多人对着屏幕看半天看不出毛病。第四条则是因为字符串字典序和数字序在样例规模较小时可能一致一旦有跨位数的考号就会露馅。5.2 一份快速的边界测试模板如果你想在本地快速验证自己代码对不对可以构造几组特殊的输入。我先分享一组最简单的5 60 90 100001 90 90 100002 90 60 100003 80 80 100004 60 60 100005 50 50这里H90L60。第一人德才双高type1第二人德够才不够type2第三人德才都低于90但德分等于才分type3第四人刚过线type4第五人才分只有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的题基本就能一眼看穿出题人想要你干什么了。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
