准备PAT甲级的朋友应该对这类题不陌生一堆学生、一堆课程输入里每个人报出自己的选课清单最后让你按课程号输出每门课的学生名单名字还得按字典序排好。这道“Student List for Course”在PAT里算一道标准的25分模拟题但很有意思的是它几乎每年都能卡住一批人。不是题目难而是很多人第一眼觉得“这不就是个排序吗”写完一提交要么内存警告要么最后一个测试点超时还有的直接在字符串比较和空桶处理上翻车。这篇文章我就把这道题从头到尾拆开讲包括我的初版实现为什么失败、换用ID索引后性能为什么提升明显、以及考场上应该避开的几个隐蔽陷阱。无论你是刚开始刷PAT的小白还是已经做过几套真题想优化写法的选手应该都能从这里拿到点东西。1. 先看题目把“人”和“课”的关系彻底理清1.1 原题约束与输入样例推演题目本身不复杂。第一行给两个数N和KN是学生总数K是课程总数。接下来N行每行先是一个学生姓名大写字母组成长度1到4然后是一个整数C代表这个学生选了几门课后面跟着C个课程编号课程编号范围是1到K。要求最后按照课程编号从1到K递增输出每门课先输出课程号和选课人数再按姓名字典序输出所有选课学生。举个最简单的例子假设输入是这样4 2 ZOE1 1 1 ANN0 1 1 BOB5 1 2 JOE4 1 1总共4个学生、2门课。ZOE1、ANN0、JOE4选了课程1BOB5选了课程2。那么正确的输出应该是1 3 ANN0 JOE4 ZOE1 2 1 BOB5注意这里课程1的输出顺序是ANN0、JOE4、ZOE1纯字母序不是输入顺序也不是学生编号顺序。2号课程只有一个人输出格式依然是“课程号 人数”占一行后面跟一个姓名。这类题的难点从来不在理解题意而在你用什么数据结构去承接“每门课有哪些学生”这个关系。1.2 最容易在开局就踩的坑先按学生建表还是先按课程建表因为输入是按学生给的所以很多人本能地先把每个学生的选课信息存下来想着后面再遍历每个学生把他塞进对应课程。这个思路不是不能用但会让代码变得很绕你需要一个“学生到课程”的映射又要反过来维护“课程到学生”的映射稍不注意就写出两层循环。正确做法是一开始就抛弃“按学生存储”的念头直接在读入过程中把学生ID塞进对应课程的桶里。也就是说你维护一个长度为K1的数组数组下标就是课程号每个桶里放的是选这门课的学生ID。这样读入完成后所有课程的学生名单已经完整躺在那里只差排序和输出了。这个转换看起来简单却是整道题最关键的一步。它决定了你的代码是清爽的80行还是混乱的150行。2. 初版实现的血泪为什么用vectorstring会心虚2.1 一个看起来完全正确的写法我第一次做这道题的时候写的版本非常直观全局定义一个vectorstring course[2510]读入学生姓名再把姓名以string形式直接push到对应课程。排序时直接用sort(course[i].begin(), course[i].end())因为string支持字典序比较天然满足题目要求。输出也简单遍历每个桶逐个打印。代码如下#include cstdio #include vector #include string #include algorithm using namespace std; vectorstring course[2510]; int main() { int n, k; scanf(%d%d, n, k); char name[5]; for (int i 0; i n; i) { int c; scanf(%s%d, name, c); for (int j 0; j c; j) { int cid; scanf(%d, cid); course[cid].push_back(string(name)); } } for (int i 1; i k; i) { sort(course[i].begin(), course[i].end()); printf(%d %d\n, i, (int)course[i].size()); for (int j 0; j course[i].size(); j) { printf(%s\n, course[i][j].c_str()); } } return 0; }这段代码逻辑上没有任何问题本地跑样例也完全正确。但你要是在PAT平台上提交就得多想一层这个程序的性能到底能不能扛住上限数据。2.2 开销到底在哪里N的最大值是40000K的最大值是2500每个学生最多选多少门课题目没有明说但理论上每个学生可以把K门课全部选一遍。即便真实测试数据不会真让总量达到上亿规模几万到几十万条“学生-课程”记录是很常见的。在这种量级下vectorstring有两个很悬的开销点。第一每次push_back(string(name))都会构造一个临时string对象涉及堆上动态分配、字符拷贝、临时对象析构。字符串虽然只有1到4个字符但架不住次数多。第二vector扩容时会搬运所有已有元素。string的拷贝构造和析构频率一高时间开销就会被明显放大。你可能觉得几百毫秒无所谓但PAT的有些测试点时间限制非常紧尤其是这题卡的是大量小字符串的重复分配和释放极端情况下能跑出接近上百万次堆操作。有的朋友会说那我预先reserve容量总行了吧。比如先给每个课程桶预留几百个位置或者读入前统计每门课人数再做第二遍填充。这能缓解一部分扩容开销但依然绕不开“把长度不固定的字符串搬进桶里”的构造代价。而且如果预留过多内存占用又会上去vectorstring本身有额外的对象开销24字节左右一个2501个桶即使每个桶是空的也存在基本开销。我在测试极端数据的时候测过一版直接构造string的实现和后面要说的ID索引方案做对比耗时差距大致在3到5倍。数据规模越大差距越明显。考试中你没法预测测试点到底有多狠所以从一开始就选择更稳的写法才是正确的策略。3. 第二版让学生ID进入课程桶用排序规则间接排姓名3.1 全局存姓名桶里存ID优化思路其实一句话就能说清不要在课程桶里直接存字符串而是存学生的整数ID。学生的姓名单独开一个全局二维字符数组存着ID和姓名通过数组下标一一对应。这样一来每个课程桶里都只存intvector在扩容和拷贝时移动的是4字节的整数开销比操作string小一个数量级。具体结构如下char name[40010][5]; vectorint course[2510];读入时学生的名字已经存进了name[i]然后每读到一个课程号cid就把学生编号i塞进course[cid]。一个人选多门课同一个ID就会出现在多个桶里这是完全正确的因为我们需要的就是“每个课程各自的选课名单”。3.2 比较器和最终代码问题来了桶里存的是学生的整数ID但题目要求按姓名排序。排序时不能直接比ID大小而要拿ID去name数组里找到对应字符串再按照字符串的字典序比较。这就要自定义sort的比较器。因为比较器需要访问全局的name数组所以name必须定义成全局变量排序函数可以直接引用它#include cstdio #include vector #include cstring #include algorithm using namespace std; char name[40010][5]; vectorint course[2510]; bool cmp(int a, int b) { return strcmp(name[a], name[b]) 0; } int main() { int n, k; scanf(%d%d, n, k); for (int i 0; i n; i) { int c; scanf(%s%d, name[i], c); for (int j 0; j c; j) { int cid; scanf(%d, cid); course[cid].push_back(i); } } for (int i 1; i k; i) { sort(course[i].begin(), course[i].end(), cmp); printf(%d %d\n, i, (int)course[i].size()); for (int j 0; j (int)course[i].size(); j) { printf(%s\n, name[course[i][j]]); } } return 0; }这段代码的排序规则是strcmp的返回值小于0时a排在b前面正好对应“姓名字典序从小到大”。因为姓名都是大写字母strcmp比较的是ASCII码序而大写字母的ASCII码序列恰好就是字典序所以放心用。你可能注意到排序的是学生ID真正比较时又要回到名字。这看似多绕了一步实际效率反而高。桶里存的是景点化后的学生索引排序时虽然比较函数要访问全局数组但这只是内存读取成本远低于string对象的动态堆操作。而且最终输出时通过name[course[i][j]]取出姓名逻辑上也顺理成章。3.3 要不要搞哈希映射说说取舍除了存ID还有人会想到把字符串形式的姓名直接编码成整数比如把每个大写字母看成26进制的一位然后整个姓名转换成一个唯一的整数键值。这样就可以把“姓名到ID”的查找从字符串比较变成整数比较甚至可以直接用二维int数组存每门课的学生编号排序时直接比较这个哈希值。我见过不少代码是这么写的。好处也很明显如果哈希函数设计得好每次比较整数比strcmp还快。但这里有几个隐患姓名长度不固定有1到4位。如果简单地把A编码成1把AA编码成1*261理论上可能出现不同字符串对应同一个哈希值的碰撞。题目约定学生姓名唯一但没有约定你的哈希函数一定不碰撞。处理碰撞需要额外设计比如把哈希值再拼上长度或者接受一定概率的碰撞后做二次验证。这在考试里是徒增心智负担。哈希编码本身没有通用性换个题目就用不上了。而“桶里存ID 全局数组存信息”这个思路几乎适用于所有PAT中涉及分组输出的题目。所以我个人的建议是除非你已经把哈希编码相关的边界条件都处理得滚瓜烂熟否则不要在这里炫技。用vectorint桶加全局名字数组的方案已经是我能找到的在“代码量、可读性、运行速度”三者之间最平衡的写法。它不需要任何前提假设也不会因为哈希设计失误而WA。4. 几个容易翻车的边界场景和考试环境提示4.1 零人选课的课程怎么输出题目要求对K门课都输出不是只输出有人选的课。所以遍历输出时必须从1循环到K而不是遍历“出现过的课程”。这也是我前面强调“用数组下标直接映射课程号”的原因如果用一个mapint, vectorint或者只记录出现过的课程编号最后还得额外补一遍所有空课程的输出反而多写代码。当某个课程桶为空时course[i].size()为0直接输出“课程号 0”换行不需要输出任何姓名。很多人在这一步会漏掉尤其是样例里没有空课程时本地测什么都对一提交就WA。可以自测一组2 3 AAA 1 1 BBB 1 2期望输出1 1 AAA 2 1 BBB 3 0注意课程3的人数必须是0而不是不输出。4.2 姓名比较的边界与strcmp的小陷阱strcmp(name[a], name[b]) 0表示a的字典序小于b。这是最常见的写法但要注意strcmp比较的是C风格字符串它会一直读到\0为止。因为姓名数组是char[5]姓名本身不会超过4个字符所以不存在越界读取问题。另一个容易翻车的点是如果你用string可以直接name[a] name[b]但如果用字符数组就千万别直接name[a] name[b]那是在比较两个字符数组的首地址结果完全随机。我见过不止一个人在这里写错排序结果诡异还以为是数据问题。还有把姓名称为“字典序”在中文翻译里容易让人疑惑。PAT原题说的是“in increasing orderalphabetically”因为姓名都是大写字母所以就是A到Z的顺序也就是ASCII码的升序。这个排序规则在strcmp下天然成立。4.3 PAT平台实测的输入输出节奏和警告处理这题数据规模不小输入输出务必用scanf和printf而不是cin和cout。即便你加了ios::sync_with_stdio(false); cin.tie(nullptr);在这道题里通常也能过但我个人在考场上还是倾向于直接上C风格的输入输出理由是少一个潜在的不确定因素。另外比较器函数cmp必须定义在全局name数组之后否则编译器不知道name是什么。如果cmp是类成员函数还需要先转成静态函数。在PAT这类平台上平时做题时养成把所有辅助数组和比较器写在全局区的习惯能省掉很多编译警告。还有一个小细节printf(%s\n, name[course[i][j]])中的name[course[i][j]]是一个char[5]类型传给printf的%s时需要隐式转换成const char*。这个转换没问题但如果你的编译器警告级别开得比较高可能会提示“format specifies type char but the argument has type char ()[5]”本质是因为你误把整个名字数组的地址传进去了。正确的传法是name[索引]而不是name[索引]。5. 做完这题后顺带把同类题型都串一遍5.1 与Course List for Student对比PAT里还有一道题叫“Course List for Student”名字正好和这题反过来。那道题输入的是课程编号加学生姓名列表最后要求输出每个学生的选课列表课程号按升序排列。两道题放一起看特别有意思它们的结构是镜像的一个按学生输出一个按课程输出。解法上那道题也要用“先存后排序”的思路只不过桶的维度是学生编号桶里存的是课程号最后对每个学生桶里的课程号做数字升序排序。我建议大家把这两道题连着刷因为它们的共同核心是先在输入阶段把原始数据拆散再按照输出维度的主键建立桶结构最后统一排序。掌握了这个模板PAT中大量“分组输出”题都能秒出思路。5.2 这类题的通用解法总结花点时间把这题的套路抽象出来你会得到一个可以反复套用的框架确定输出维度。这道题输出维度是课程所以桶的索引是课程号。确定桶里存什么。这道题桶里存学生ID而不是姓名本身因为ID更轻量。确定比较规则。这道题按姓名升序所以比较器通过ID访问全局姓名数组。统一在输出前排序不要边读边排。输出时遍历所有桶包括空桶保证输出行不缺。第4点值得再强调一下。有些朋友在读入每个学生时就立刻把ID插进对应课程并马上排序看起来每时每刻桶都是有序的实际上每插入一个学生就要触发一次排序复杂度会退化得非常难看。正确做法是等所有输入读完再对每个桶分别sort。排序的总代价跟所有桶各自的大小有关这样才是最省的。这道题做完我还有一个很深的体会PAT考场上真正拉开差距的往往不是你会不会某个高深算法而是能不能在压力下仍然选择最稳妥的数据结构。用vectorstring写这题运气好能过运气不好就挂在某个极端用例上而用ID索引写这题几乎是稳的。平时练习时有意识地把“贪图方便”的写法换成“性能更稳”的写法考场上才不会犯同样的错误。