PAT Basic 1095. 解码PAT准考证
1. 题目描述：
PAT 准考证号由 4 部分组成：
- 第 1 位是级别，即
T代表顶级；A代表甲级；B代表乙级； - 第 2~4 位是考场编号，范围从 101 到 999；
- 第 5~10 位是考试日期，格式为年、月、日顺次各占 2 位；
- 最后 11~13 位是考生编号，范围从 000 到 999。
现给定一系列考生的准考证号和他们的成绩，请你按照要求输出各种统计信息。
2. 输入格式：
输入首先在一行中给出两个正整数 \(N\)（\(≤10^4\)）和 \(M\)（\(≤100\)），分别为考生人数和统计要求的个数。
接下来 \(N\) 行，每行给出一个考生的准考证号和其分数（在区间 \([0,100]\) 内的整数），其间以空格分隔。
考生信息之后，再给出 \(M\) 行，每行给出一个统计要求，格式为：类型 指令，其中
类型为 1 表示要求按分数非升序输出某个指定级别的考生的成绩，对应的指令则给出代表指定级别的字母；类型为 2 表示要求将某指定考场的考生人数和总分统计输出，对应的指令则给出指定考场的编号；类型为 3 表示要求将某指定日期的考生人数分考场统计输出，对应的指令则给出指定日期，格式与准考证上日期相同。
3. 输出格式：
对每项统计要求，首先在一行中输出 Case #: 要求，其中 # 是该项要求的编号，从 1 开始；要求 即复制输入给出的要求。随后输出相应的统计结果：
类型为 1 的指令，输出格式与输入的考生信息格式相同，即准考证号 成绩。对于分数并列的考生，按其准考证号的字典序递增输出（题目保证无重复准考证号）；类型为 2 的指令，按人数 总分的格式输出；类型为 3 的指令，输出按人数非递增顺序，格式为考场编号 总人数。若人数并列则按考场编号递增顺序输出。
如果查询结果为空，则输出 NA。
4. 输入样例：
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
5. 输出样例：
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
6. 性能要求：
Code Size Limit
16 KB
Time Limit
200 ms
Memory Limit
64 MB
思路：
考察基础IO，定义结构体Student存储考生信息，根据题意分别编写处理三种指令的代码即可。这里我定义子函数handleDirect()处理指令，指令1和指令2的处理比较常规，主要说下我处理指令3的思路：首先筛选出符合指定日期的记录，然后根据准考证号对这些记录进行排序，那么理论上相同考场的记录会连在一起，再根据之前压缩字符串的思路PAT Basic 1078. 字符串压缩与解压 对每一考场的人数计数即可，额外定义结构体Dir3存储各个考场的信息，最后根据人数和考场编号对统计出的考场信息进行排序和输出。
第一次提交时testpoint3报Time Limit Exceeded，回想起之前看别人的博客提到最好不要直接拷贝、移动结构体本身，于是将handleDirect()中的逻辑处理部分改为定义结构体指针数组，存储和排序时使用结构体指针而不是结构体本身，改完后testpoint3又报wrong answer。。。排查了好久才发现是因为准考证号是以级别开头，直接排序的话相同考场的记录可能没有连在一起，疏忽了这一点。。。修改排序函数sort_id()后AC。
My Code:
// #include <stdio.h>
// #include <stdlib.h> // malloc header, qsort header
// #include <string.h> // strcmp header, strncpy header, strcpy header
// typedef struct student
// {
// char id[14];
// int grade;
// } Student;
// typedef struct dir3
// {
// char room[4];
// int count;
// } Dir3;
// void handleDirect(Student *pStu, int stuCount, int dirType, const char *direct);
// int sort_dir1(const void *p1, const void *p2);
// int sort_id(const void *p1, const void *p2);
// int sort_dir3(const void *p1, const void *p2);
// // first submit testpoint3 Time Limit Exceeded
// int main(void)
// {
// int stuCount=0, directCount=0;
// Student *pStu = NULL;
// int i=0; // iterator
// int dirType=0;
// char directive[7] = "";
// scanf("%d%d", &stuCount, &directCount);
// pStu = (Student *)malloc(sizeof(Student) * stuCount); // allocate memory
// for(i=0; i<stuCount; ++i)
// {
// scanf("%s%d", pStu[i].id, &pStu[i].grade);
// //printf("%s %d\n", pStu[i].id, pStu[i].grade); // test input
// }
// for(i=0; i<directCount; ++i)
// {
// scanf("%d%s", &dirType, directive);
// //printf("%d %s\n", dirType, directive); // test input
// printf("Case %d: %d %s\n", i+1, dirType, directive);
// handleDirect(pStu, stuCount, dirType, directive);
// }
// free(pStu); // free heap memory
// return 0;
// }
// void handleDirect(Student *pStu, int stuCount, int dirType, const char *direct)
// {
// Student *pRes = NULL;
// int resCount = 0; // result iterator
// int i=0; // iterator
// /* var for directive2 */
// char examRoom[4] = "";
// int gradeSum=0;
// /* var for directive3 */
// char date[7] = "";
// Dir3 *pDir3 = NULL;
// int dir3Count=0, tempCount=0;
// char lastRoom[4] = "", tempRoom[4] = ""; // this must be initialize, for strncpy doesn't add '\0'
// pRes = (Student *)malloc(sizeof(Student) * stuCount); // allocate heap memory
// switch(dirType)
// {
// case 1: // output a class grade in descending order
// resCount = 0;
// for(i=0; i<stuCount; ++i)
// {
// if(pStu[i].id[0] == direct[0]) // is this class
// {
// pRes[resCount++] = pStu[i];
// }
// }
// if(resCount) // have corresponding info
// {
// qsort(pRes, resCount, sizeof(Student), sort_dir1);
// for(i=0; i<resCount; ++i)
// {
// printf("%s %d\n", pRes[i].id, pRes[i].grade);
// }
// }
// else // no corresponding info
// {
// printf("NA\n");
// }
// break;
// case 2: //
// resCount = 0;
// gradeSum = 0;
// for(i=0; i<stuCount; ++i)
// {
// strncpy(examRoom, pStu[i].id+1, 3); // extract examRoom
// if(!strcmp(examRoom, direct)) // is this room
// {
// ++resCount;
// gradeSum += pStu[i].grade;
// }
// }
// if(resCount) // have corresponding info
// {
// printf("%d %d\n", resCount, gradeSum);
// }
// else // no corresponding info
// {
// printf("NA\n");
// }
// break;
// case 3:
// resCount = 0;
// for(i=0; i<stuCount; ++i)
// {
// strncpy(date, pStu[i].id+4, 6); // extract date
// if(!strcmp(date, direct)) // is this date
// {
// pRes[resCount++] = pStu[i];
// }
// }
// //printf("resCount: %d\n", resCount);
// if(resCount) // have corresponding info
// {
// qsort(pRes, resCount, sizeof(Student), sort_id);
// // for(i=0; i<resCount; ++i)
// // {
// // printf("%s %d\n", pRes[i].id, pRes[i].grade);
// // }
// pDir3 = (Dir3 *)malloc(sizeof(Dir3) * resCount);
// dir3Count = 0;
// tempCount = 1;
// strncpy(lastRoom, pRes[0].id+1, 3); // extract examRoom
// //printf("lastRoom: %s, strlen(lastRoom): %d\n", lastRoom, strlen(lastRoom)); //strncpy need add '\0' manually
// for(i=1; i<resCount; ++i)
// {
// strncpy(tempRoom, pRes[i].id+1, 3); // extract examRoom
// if(!strcmp(lastRoom, tempRoom)) // have continous same examRoom
// {
// ++tempCount;
// }
// else // does'n have continous same examRoom, need to output lastRoom
// {
// strcpy(pDir3[dir3Count].room, lastRoom);
// pDir3[dir3Count].count = tempCount;
// ++dir3Count;
// tempCount = 1;
// }
// strcpy(lastRoom, tempRoom); // update lastRoom
// }
// // tail handle
// strcpy(pDir3[dir3Count].room, lastRoom);
// pDir3[dir3Count].count = tempCount;
// ++dir3Count;
// qsort(pDir3, dir3Count, sizeof(Dir3), sort_dir3);
// for(i=0; i<dir3Count; ++i)
// {
// printf("%s %d\n", pDir3[i].room, pDir3[i].count);
// }
// }
// else // no corresponding info
// {
// printf("NA\n");
// }
// break;
// default:
// break;
// }
// free(pRes); // release heap memory
// free(pDir3);
// return;
// }
// int sort_dir1(const void *p1, const void *p2)
// {
// Student *pLeft = (Student *)p1;
// Student *pRight = (Student *)p2;
// if(pRight->grade != pLeft->grade)
// {
// return (pRight->grade - pLeft->grade);
// }
// else // grade is equal
// {
// return strcmp(pLeft->id, pRight->id);
// }
// }
// int sort_id(const void *p1, const void *p2)
// {
// Student *pLeft = (Student *)p1;
// Student *pRight = (Student *)p2;
// return strcmp(pLeft->id, pRight->id);
// }
// int sort_dir3(const void *p1, const void *p2)
// {
// Dir3 *pLeft = (Dir3 *)p1;
// Dir3 *pRight = (Dir3 *)p2;
// if(pLeft->count != pRight->count)
// {
// return (pRight->count - pLeft->count);
// }
// else // have same count
// {
// return strcmp(pLeft->room, pRight->room);
// }
// }
#include <stdio.h>
#include <stdlib.h> // malloc header, qsort header
#include <string.h> // strcmp header, strncpy header, strcpy header
typedef struct student
{
char id[14];
int grade;
} Student;
typedef struct dir3
{
char room[4];
int count;
} Dir3;
void handleDirect(Student *pStu, int stuCount, int dirType, const char *direct);
int sort_dir1(const void *p1, const void *p2);
int sort_id(const void *p1, const void *p2);
int sort_dir3(const void *p1, const void *p2);
// after rectify, testpoint3 wrong answer
int main(void)
{
int stuCount=0, directCount=0;
Student *pStu = NULL;
int i=0; // iterator
int dirType=0;
char directive[7] = "";
scanf("%d%d", &stuCount, &directCount);
pStu = (Student *)malloc(sizeof(Student) * stuCount); // allocate memory
for(i=0; i<stuCount; ++i)
{
scanf("%s%d", pStu[i].id, &pStu[i].grade);
//printf("%s %d\n", pStu[i].id, pStu[i].grade); // test input
}
for(i=0; i<directCount; ++i)
{
scanf("%d%s", &dirType, directive);
//printf("%d %s\n", dirType, directive); // test input
printf("Case %d: %d %s\n", i+1, dirType, directive);
handleDirect(pStu, stuCount, dirType, directive);
}
free(pStu); // free heap memory
return 0;
}
void handleDirect(Student *pStu, int stuCount, int dirType, const char *direct)
{
//Student *pRes = NULL;
Student **pRes;
int resCount = 0; // result iterator
int i=0; // iterator
/* var for directive2 */
char examRoom[4] = "";
int gradeSum=0;
/* var for directive3 */
char date[7] = "";
Dir3 *pDir3 = NULL;
int dir3Count=0, tempCount=0;
char lastRoom[4] = "", tempRoom[4] = ""; // this must be initialize, for strncpy doesn't add '\0'
//pRes = (Student *)malloc(sizeof(Student) * stuCount); // allocate heap memory
pRes = (Student **)malloc(sizeof(Student *) * stuCount); // allocate pointer of struct instead of struct itself
switch(dirType)
{
case 1: // output a class grade in descending order
resCount = 0;
for(i=0; i<stuCount; ++i)
{
if(pStu[i].id[0] == direct[0]) // is this class
{
pRes[resCount++] = &pStu[i];
}
}
if(resCount) // have corresponding info
{
qsort(pRes, resCount, sizeof(Student *), sort_dir1);
for(i=0; i<resCount; ++i)
{
printf("%s %d\n", pRes[i]->id, pRes[i]->grade);
}
}
else // no corresponding info
{
printf("NA\n");
}
break;
case 2: //
resCount = 0;
gradeSum = 0;
for(i=0; i<stuCount; ++i)
{
strncpy(examRoom, pStu[i].id+1, 3); // extract examRoom
if(!strcmp(examRoom, direct)) // is this room
{
++resCount;
gradeSum += pStu[i].grade;
}
}
if(resCount) // have corresponding info
{
printf("%d %d\n", resCount, gradeSum);
}
else // no corresponding info
{
printf("NA\n");
}
break;
case 3:
resCount = 0;
for(i=0; i<stuCount; ++i)
{
strncpy(date, pStu[i].id+4, 6); // extract date
if(!strcmp(date, direct)) // is this date
{
pRes[resCount++] = &pStu[i];
}
}
//printf("resCount: %d\n", resCount);
if(resCount) // have corresponding info
{
qsort(pRes, resCount, sizeof(Student *), sort_id);
// for(i=0; i<resCount; ++i)
// {
// printf("%s %d\n", pRes[i]->id, pRes[i]->grade);
// }
pDir3 = (Dir3 *)malloc(sizeof(Dir3) * resCount);
dir3Count = 0;
tempCount = 1;
strncpy(lastRoom, pRes[0]->id+1, 3); // extract examRoom
lastRoom[3] = 0;
//printf("lastRoom: %s, strlen(lastRoom): %d\n", lastRoom, strlen(lastRoom)); //strncpy need add '\0' manually
for(i=1; i<resCount; ++i)
{
strncpy(tempRoom, pRes[i]->id+1, 3); // extract examRoom
tempRoom[3] = 0;
if(!strcmp(lastRoom, tempRoom)) // have continous same examRoom
{
++tempCount;
}
else // does'n have continous same examRoom, need to output lastRoom
{
strcpy(pDir3[dir3Count].room, lastRoom);
pDir3[dir3Count].count = tempCount;
++dir3Count;
tempCount = 1;
}
strcpy(lastRoom, tempRoom); // update lastRoom
}
// tail handle
strcpy(pDir3[dir3Count].room, lastRoom);
pDir3[dir3Count].count = tempCount;
++dir3Count;
qsort(pDir3, dir3Count, sizeof(Dir3), sort_dir3);
for(i=0; i<dir3Count; ++i)
{
printf("%s %d\n", pDir3[i].room, pDir3[i].count);
}
}
else // no corresponding info
{
printf("NA\n");
}
break;
default:
break;
}
free(pRes); // release heap memory
free(pDir3);
return;
}
int sort_dir1(const void *p1, const void *p2)
{
Student *pLeft = *(Student **)p1;
Student *pRight = *(Student **)p2;
if(pRight->grade != pLeft->grade)
{
return (pRight->grade - pLeft->grade);
}
else // grade is equal
{
return strcmp(pLeft->id, pRight->id);
}
}
int sort_id(const void *p1, const void *p2)
{
Student *pLeft = *(Student **)p1;
Student *pRight = *(Student **)p2;
return strcmp(pLeft->id+1, pRight->id+1); // here fixed testpoint3
}
int sort_dir3(const void *p1, const void *p2)
{
Dir3 *pLeft = (Dir3 *)p1;
Dir3 *pRight = (Dir3 *)p2;
if(pLeft->count != pRight->count)
{
return (pRight->count - pLeft->count);
}
else // have same count
{
return strcmp(pLeft->room, pRight->room);
}
}