准备PAT甲级的朋友应该对这类题不陌生：一堆学生、一堆课程，输入里每个人报出自己的选课清单，最后让你按课程号输出每门课的学生名单，名字还得按字典序排好。这道“Student List for Course”在PAT里算一道标准的25分模拟题，但很有意思的是，它几乎每年都能卡住一批人。不是题目难，而是很多人第一眼觉得“这不就是个排序吗”，写完一提交，要么内存警告，要么最后一个测试点超时，还有的直接在字符串比较和空桶处理上翻车。这篇文章我就把这道题从头到尾拆开讲，包括我的初版实现为什么失败、换用ID索引后性能为什么提升明显、以及考场上应该避开的几个隐蔽陷阱。无论你是刚开始刷PAT的小白，还是已经做过几套真题想优化写法的选手，应该都能从这里拿到点东西。
1. 先看题目：把“人”和“课”的关系彻底理清
1.1 原题约束与输入样例推演
题目本身不复杂。第一行给两个数N和K，N是学生总数，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选了课程1，BOB5选了课程2。那么正确的输出应该是：
1 3 ANN0 JOE4 ZOE1 2 1 BOB5注意这里课程1的输出顺序是ANN0、JOE4、ZOE1，纯字母序，不是输入顺序，也不是学生编号顺序。2号课程只有一个人，输出格式依然是“课程号 人数”占一行，后面跟一个姓名。
这类题的难点从来不在理解题意，而在你用什么数据结构去承接“每门课有哪些学生”这个关系。
1.2 最容易在开局就踩的坑：先按学生建表，还是先按课程建表
因为输入是按学生给的，所以很多人本能地先把每个学生的选课信息存下来，想着后面再遍历每个学生，把他塞进对应课程。这个思路不是不能用，但会让代码变得很绕：你需要一个“学生到课程”的映射，又要反过来维护“课程到学生”的映射，稍不注意就写出两层循环。
正确做法是一开始就抛弃“按学生存储”的念头，直接在读入过程中把学生ID塞进对应课程的桶里。也就是说，你维护一个长度为K+1的数组，数组下标就是课程号，每个桶里放的是选这门课的学生ID。这样读入完成后，所有课程的学生名单已经完整躺在那里，只差排序和输出了。
这个转换看起来简单，却是整道题最关键的一步。它决定了你的代码是清爽的80行还是混乱的150行。
2. 初版实现的血泪：为什么用vector<string>会心虚
2.1 一个看起来完全正确的写法
我第一次做这道题的时候，写的版本非常直观：全局定义一个vector<string> course[2510]，读入学生姓名，再把姓名以string形式直接push到对应课程。排序时直接用sort(course[i].begin(), course[i].end())，因为string支持字典序比较，天然满足题目要求。输出也简单，遍历每个桶，逐个打印。
代码如下：
#include <cstdio> #include <vector> #include <string> #include <algorithm> using namespace std; vector<string> 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的最大值是40000，K的最大值是2500，每个学生最多选多少门课题目没有明说，但理论上每个学生可以把K门课全部选一遍。即便真实测试数据不会真让总量达到上亿规模，几万到几十万条“学生-课程”记录是很常见的。在这种量级下，vector<string>有两个很悬的开销点。
第一，每次push_back(string(name))都会构造一个临时string对象，涉及堆上动态分配、字符拷贝、临时对象析构。字符串虽然只有1到4个字符，但架不住次数多。第二，vector扩容时，会搬运所有已有元素。string的拷贝构造和析构频率一高，时间开销就会被明显放大。你可能觉得几百毫秒无所谓，但PAT的有些测试点时间限制非常紧，尤其是这题卡的是大量小字符串的重复分配和释放，极端情况下能跑出接近上百万次堆操作。
有的朋友会说，那我预先reserve容量总行了吧。比如先给每个课程桶预留几百个位置，或者读入前统计每门课人数再做第二遍填充。这能缓解一部分扩容开销，但依然绕不开“把长度不固定的字符串搬进桶里”的构造代价。而且如果预留过多，内存占用又会上去：vector<string>本身有额外的对象开销（24字节左右一个），2501个桶即使每个桶是空的，也存在基本开销。
我在测试极端数据的时候测过一版直接构造string的实现，和后面要说的ID索引方案做对比，耗时差距大致在3到5倍。数据规模越大，差距越明显。考试中你没法预测测试点到底有多狠，所以从一开始就选择更稳的写法才是正确的策略。
3. 第二版：让学生ID进入课程桶，用排序规则间接排姓名
3.1 全局存姓名，桶里存ID
优化思路其实一句话就能说清：不要在课程桶里直接存字符串，而是存学生的整数ID。学生的姓名单独开一个全局二维字符数组存着，ID和姓名通过数组下标一一对应。这样一来，每个课程桶里都只存int，vector在扩容和拷贝时移动的是4字节的整数，开销比操作string小一个数量级。
具体结构如下：
char name[40010][5]; vector<int> 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]; vector<int> 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*26+1，理论上可能出现不同字符串对应同一个哈希值的碰撞。题目约定学生姓名唯一，但没有约定你的哈希函数一定不碰撞。 - 处理碰撞需要额外设计，比如把哈希值再拼上长度，或者接受一定概率的碰撞后做二次验证。这在考试里是徒增心智负担。
- 哈希编码本身没有通用性，换个题目就用不上了。而“桶里存ID + 全局数组存信息”这个思路几乎适用于所有PAT中涉及分组输出的题目。
所以我个人的建议是：除非你已经把哈希编码相关的边界条件都处理得滚瓜烂熟，否则不要在这里炫技。用vector<int>桶加全局名字数组的方案，已经是我能找到的在“代码量、可读性、运行速度”三者之间最平衡的写法。它不需要任何前提假设，也不会因为哈希设计失误而WA。
4. 几个容易翻车的边界场景和考试环境提示
4.1 零人选课的课程怎么输出
题目要求对K门课都输出，不是只输出有人选的课。所以遍历输出时，必须从1循环到K，而不是遍历“出现过的课程”。这也是我前面强调“用数组下标直接映射课程号”的原因：如果用一个map<int, vector<int>>或者只记录出现过的课程编号，最后还得额外补一遍所有空课程的输出，反而多写代码。
当某个课程桶为空时，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 order（alphabetically）”，因为姓名都是大写字母，所以就是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考场上真正拉开差距的，往往不是你会不会某个高深算法，而是能不能在压力下仍然选择最稳妥的数据结构。用vector<string>写这题，运气好能过，运气不好就挂在某个极端用例上；而用ID索引写这题，几乎是稳的。平时练习时有意识地把“贪图方便”的写法换成“性能更稳”的写法，考场上才不会犯同样的错误。
