题目
PAT 准考证号由 4 部分组成：
- 第 1 位是级别，即 T 代表顶级；A 代表甲级；B 代表乙级；
- 第 2~4 位是考场编号，范围从 101 到 999；
- 第 5~10 位是考试日期，格式为年、月、日顺次各占 2 位；
- 最后 11~13 位是考生编号，范围从 000 到 999。
现给定一系列考生的准考证号和他们的成绩，请你按照要求输出各种统计信息。
输入格式：
输入首先在一行中给出两个正整数 N（≤
）和 M（≤100），分别为考生人数和统计要求的个数。
接下来 N 行，每行给出一个考生的准考证号和其分数（在区间 [0,100] 内的整数），其间以空格分隔。
考生信息之后，再给出 M 行，每行给出一个统计要求，格式为：类型 指令，其中
- 类型 为 1 表示要求按分数非升序输出某个指定级别的考生的成绩，对应的 指令 则给出代表指定级别的字母；
- 类型 为 2 表示要求将某指定考场的考生人数和总分统计输出，对应的 指令 则给出指定考场的编号；
- 类型 为 3 表示要求将某指定日期的考生人数分考场统计输出，对应的 指令 则给出指定日期，格式与准考证上日期相同。
输出格式：
对每项统计要求，首先在一行中输出 Case #: 要求，其中 # 是该项要求的编号，从 1 开始；要求 即复制输入给出的要求。随后输出相应的统计结果：
- 类型 为 1 的指令，输出格式与输入的考生信息格式相同，即 准考证号 成绩。对于分数并列的考生，按其准考证号的字典序递增输出（题目保证无重复准考证号）；
- 类型 为 2 的指令，按 人数 总分 的格式输出；
- 类型 为 3 的指令，输出按人数非递增顺序，格式为 考场编号 总人数。若人数并列则按考场编号递增顺序输出。
如果查询结果为空，则输出 NA。
输入样例：
8 4
B123180908127 99
B102180908003 86
A112180318002 98
T107150310127 62
A107180908108 100
T123180908010 78
B112160918035 88
A107180908021 98
1 A
2 107
3 180908
2 999
输出样例：
Case 1: 1 A
A107180908108 100
A107180908021 98
A112180318002 98
Case 2: 2 107
3 260
Case 3: 3 180908
107 2
123 2
102 1
Case 4: 2 999
NA
前置知识
首先做题目时候一个好习惯是：我们先去看一眼数据规模。题目中
并且 
，时间限制是200ms，所以如果采用冒泡排序等时间复杂度最坏为
的排序算法的话，很容易超出时间限制。
在C语言中，有一种快速排序函数qsort，它的时间复杂度是
，被定义在头文件stdlib.h里，它的函数原型是：
void qsort(void*base,size_t num,size_t size,int(__cdecl*compare)(const void*,const void*));
第一个参数：需要排序的数组的首地址
第二个参数：数组的长度
第三个参数：需要排序的数据类型的大小（经常在这一块填sizeof(数据类型)）
第四个参数：需要自定义的排序函数。
排序函数原型必须是：
int cmp(const void*, const void*);
也就是说传进去两个void指针，先要强制转换成你的数据类型，比如如果你要排序的类型是int，并且按照降序排序，你可以写：
int cmp(const void *a, const void *b){
int *x=(int*)a;
int *y=(int*)b;
if (*x!=*y) return *y-*x;
return 0;
}
然后在main函数里，使用qsort函数，参照以下格式：
qsort(arr, len, sizeof(int), cmp);
解题过程
一、定义两个数据类型
为了方便使用qsort函数，我们事先定义两个数据类型。
EXAM：存储学生的各项信息。
typedef struct{
char no[20]; //准考证号
char test; //考试类型
int room; //考场编号
int date; //考试日期
int id; //考生编号
int score; //学生成绩
}EXAM;
OUTPUT：在类型3中的排序和输出。
typedef struct{
int room; //考场编号
int cnt; //考试人数
}OUTPUT;
二、处理排序函数
类型1
题目要求：按分数非升序输出某个指定级别的考生的成绩，对于分数并列的考生，按其准考证号的字典序递增输出。
类型2
题目要求：将某指定考场的考生人数和总分统计输出。
所以我们先按照考场号进行排序，把同一个考场号的学生聚在一起。
类型3
题目要求：将某指定日期的考生人数分考场统计输出，输出按人数非递增顺序，若人数并列则按考场编号递增顺序输出。
所以我们先按照日期进行排序，把同一个考试日期的学生聚在一起。
然后在处理指令部分，计算完考场人数之后，我们按照人数非递增顺序再排一遍。
代码实现
//按照分数的排序函数
int cmp_score(const void *a,const void *b){
EXAM *x=(EXAM*)a;
EXAM *y=(EXAM*)b;
if (x->score!=y->score) return y->score-x->score;
return strcmp(x->no,y->no);
}
//按照考场号的排序函数
int cmp_room(const void *a,const void *b){
EXAM *x=(EXAM*)a;
EXAM *y=(EXAM*)b;
if (x->room!=y->room) return x->room-y->room;
return 0;
}
//按照日期的排序函数
int cmp_date(const void *a,const void *b){
EXAM *x=(EXAM*)a;
EXAM *y=(EXAM*)b;
if (x->date!=y->date) return x->date-y->date;
if (x->room!=y->room) return x->room-y->room;
return 0;
}
//按照考生人数的排序函数
int cmp_cnt(const void *a,const void *b){
OUTPUT *x=(OUTPUT*)a;
OUTPUT *y=(OUTPUT*)b;
if (x->cnt!=y->cnt) return y->cnt-x->cnt;
if (x->room!=y->room) return x->room-y->room;
return 0;
}
三、main函数逻辑
1.解析准考证
在C语言，既没有像Python一样的切片操作，也没有像C++一样截取子串的substr函数，所以我们只能手动解析，并且做一个循环把字符串转为整数。注意看清题目的下标，不要搞错了。
int main(){
int N,M;
scanf("%d %d",&N,&M);
EXAM stu[N]; //定义结构数组stu，用于存储原数据
for (int i=0;i<N;i++){
scanf("%s %d",stu[i].no,&stu[i].score); //格式化读取输入，注意%s后面的参数不用加取地址符号&
//解析准考证
stu[i].test=stu[i].no[0];
stu[i].room=0,stu[i].date=0,stu[i].id=0;
//字符串转整型
for (int j=1;j<4;j++){
stu[i].room=stu[i].room*10+stu[i].no[j]-'0';
}
for (int j=4;j<10;j++){
stu[i].date=stu[i].date*10+stu[i].no[j]-'0';
}
for (int j=10;j<13;j++){
stu[i].id=stu[i].id*10+stu[i].no[j]-'0';
}
}
2.数据预处理
有一些人可能会跳过这一步操作，直接进入下一步，去处理每一个指令。这样做有一个坏处，我举一个极端例子：
如果M取100，有33个指令在查B考试的排名，有33个指令在查A考试的排名，有34个指令在查T考试的排名。如果不做预处理的话，要做100遍qsort，但是实际上我们只做了3遍有效的qsort，剩下97遍都是在浪费时间。
同样的，对于类型2和3，每次去从原数据开始处理，不仅费时而且费力。
这就是我们要做数据预处理的原因。
对于类型1，我们先把原数据按照考试类型分为三类，然后直接预先调用qsort排序完成。
EXAM stu_B[N],stu_A[N],stu_T[N]; //定义三个结构数组，用来分类存储数据
int idx1=0,idx2=0,idx3=0; //三个下标，分别对应BAT
//按考试类型存储数据
for (int i=0;i<N;i++){
if (stu[i].test=='B'){
stu_B[idx1++]=stu[i];
}else if (stu[i].test=='A'){
stu_A[idx2++]=stu[i];
}else if (stu[i].test=='T'){
stu_T[idx3++]=stu[i];
}
}
//这时候的三个下标变成了各自类的学生数，使用qsort函数进行按成绩的排序
if (idx1) qsort(stu_B,idx1,sizeof(EXAM),cmp_score);
if (idx2) qsort(stu_A,idx2,sizeof(EXAM),cmp_score);
if (idx3) qsort(stu_T,idx3,sizeof(EXAM),cmp_score);
对于类型2和3，我们先排序，将相同room/date的数据聚在一起，方便之后的查找和处理。
//定义两个结构数组，分别对应类型2和3的任务，并按照各自的逻辑进行排序
EXAM stu_room[N],stu_date[N];
for (int i=0;i<N;i++){
stu_room[i]=stu[i];
stu_date[i]=stu[i];
}
qsort(stu_room,N,sizeof(EXAM),cmp_room);
qsort(stu_date,N,sizeof(EXAM),cmp_date);
3.处理输入的指令
在这里，如果直接开始上手就写for循环，你会踩到一个专属于C语言的坑——
你的缓冲区不太干净，准确地说，在执行完下面这一行的时候，缓冲区里还留了个换行符。
scanf("%s %d",stu[i].no,&stu[i].score);
所以我们要把它用getchar()吃掉。
如果不吃掉的话，下面用fgets读取的时候，第一次就会读到一个空行。
3.1 读取每一行的输入
并且输出一行case+要求编号+复制要求。
//处理输入的指令
getchar(); //吃掉换行符（scanf读整型数据之后，在缓冲区留下一个'\\n'）
for (int i=0;i<M;i++){
char buf[50];
char type;
fgets(buf,50,stdin);
int len=strlen(buf);
if (buf[len-1]=='\\n'){
buf[len-1]='\\0';
len–;
}
printf("Case %d: %s\\n",i+1,buf); //按照题目要求输出要求编号，复制要求
type=buf[0]; //type是该要求的类型
3.2 处理类型1
在这里我们已经通过数据预处理排序完成了，所以只需要查表就行，时间复杂度可以忽略不计。
注意处理边界情况。边界情况有两种：
1️⃣你要查的那个考试类型，没有学生。
2️⃣你输入了非法的考试类型（你输入了非BAT的其他字母）。
严谨起见，这两种情况都要输出 NA。
if (type=='1'){
char cur_test; //要求处理的考试类型
int cur_idx=2;
while (!(buf[cur_idx]>='A' && buf[cur_idx]<='Z')){
cur_idx++; //防御性编程，万一有多个空格，直接跳过，找到要求处理的考试类型
}
cur_test=buf[cur_idx];
if (cur_test=='B'){
if (!idx1){
printf("NA\\n"); //边界情况，该类型没有学生，下同
}else{
for (int j=0;j<idx1;j++){ //直接输出预处理完的表，下同
printf("%s %d\\n",stu_B[j].no,stu_B[j].score);
}
}
}else if (cur_test=='A'){
if (!idx2){
printf("NA\\n");
}else{
for (int j=0;j<idx2;j++){
printf("%s %d\\n",stu_A[j].no,stu_A[j].score);
}
}
}else if (cur_test=='T'){
if (!idx3){
printf("NA\\n");
}else{
for (int j=0;j<idx3;j++){
printf("%s %d\\n",stu_T[j].no,stu_T[j].score);
}
}
}else{
printf("NA\\n"); //边界情况，输入的不是BAT中的任意一个
}
3.3 处理类型2
我们在数据预处理阶段已经得到了一个数组，它按照考场编号已经分成了几大块。我们只需要找到需要查询的考场编号在数组中的那一大块的起始下标和终止下标就行了。然后累加一下总分。
}else if (type=='2'){
int cur_room=0,start=0,end=0;
for (int j=2;j<len;j++){
if (buf[j]>='0' && buf[j]<='9'){ //跳过所有非数字字符，下同
cur_room=cur_room*10+buf[j]-'0'; //字符串转整型，下同
}
}
while (start<N && stu_room[start].room!=cur_room){
start++; //找到第一个对应的下标start
}
if (start==N){ //找了一遍没找到
printf("NA\\n");
continue;
}
end=start;
while (end<N && stu_room[end].room==cur_room){
end++; //找到最后一个对应的下标，是end-1
}
int cnt=end-start,sum=0;
for (int j=start;j<end;j++){
sum+=stu_room[j].score; //统计当前对应的总分
}
printf("%d %d\\n",cnt,sum);
3.4 处理类型3
我们先按3.3的逻辑找到需要处理的这一块的起始下标和终止下标：
}else if (type=='3'){
int cur_date=0,start=0,end=0;
for (int j=2;j<len;j++){
if (buf[j]>='0' && buf[j]<='9'){
cur_date=cur_date*10+buf[j]-'0';
}
}
while (start<N && stu_date[start].date!=cur_date){
start++;
}
if (start==N){
printf("NA\\n");
continue;
}
end=start;
while (end<N && stu_date[end].date==cur_date){
end++;
}
因为题目说需要统计每个考场的总人数，所以我们再按考场进行分块并且排序，最后输出：
int idx=start,offset=1,idx_new=0; //idx处在[start,end)之间，offset是偏移量
OUTPUT outp[end-start]; //建立结构数组outp，处理排序和输出
while (idx<end){ //idx严格小于end
while (idx+offset<end && stu_date[idx].room==stu_date[idx+offset].room){
offset++; //注意边界条件，所有被访问的下标都要小于end
}
outp[idx_new].room=stu_date[idx].room;
outp[idx_new].cnt=offset; //offset即为连续的区间长度，就是当前考场的人数
idx_new++;
idx+=offset; //idx直接跳过这一块，处理下一块
offset=1; //offset重新置1
}
qsort(outp,idx_new,sizeof(OUTPUT),cmp_cnt); //outp按照考生人数排序
for (int j=0;j<idx_new;j++){
printf("%d %d\\n",outp[j].room,outp[j].cnt);
}
}
}
}
容易WA的点
1. 解析准考证时，下标不准确导致解析错位。
2. 在混用scanf和fgets时，没有考虑缓冲区的残留换行符。
3. 在3.4中，对于下标越界的控制不当。在这里给出几种错误样例：
//错误1：下标越界限制条件写在后面
while (idx<end){ //idx严格小于end
while (stu_date[idx].room==stu_date[idx+offset].room && idx+offset<end){
offset++; //注意边界条件，所有被访问的下标都要小于end
}
…
}
//这样会导致在下标越界时候，后面的条件idx+offset<end来不及保护。
//也就是在idx+offset==end时候，C语言会先执行stu_date[idx].room==stu_date[idx+offset].room
//然后再看是否满足idx+offset<end。这就导致内存越界访问。
//错误2：下标越界条件写错，如下例：
while (idx+offset<end){ //idx严格小于end
while (idx+offset<end && stu_date[idx].room==stu_date[idx+offset].room){
offset++; //注意边界条件，所有被访问的下标都要小于end
}
…
}
//这会导致下标为end-1的数据无法进入while循环。
//但这个数据是合法的，需要进入外层循环而不进入内层循环。
所以，写完代码之后，需要对代码进行检查，仔细调试，注意边界情况和对下标的控制。
总结
这道题目已经不是单纯的程序设计题了，而要求读者具有“工程化”和“结构化”的思维，其中通过数据预处理来减少不必要的计算、预先归类避免从原数据直接进行的暴力查找，这两个思想是提高效率的关键。
