PAT Basic 1100. 校庆
1. 题目描述：
2019 年浙江大学将要庆祝成立 122 周年。为了准备校庆，校友会收集了所有校友的身份证号。现在需要请你编写程序，根据来参加校庆的所有人士的身份证号，统计来了多少校友。
2. 输入格式：
输入在第一行给出不超过 \(10^5\) 的正整数 N，随后 N 行，每行给出一位校友的身份证号（18 位由数字和大写字母X组成的字符串）。题目保证身份证号不重复。
随后给出前来参加校庆的所有人士的信息：首先是一个不超过 \(10^5\) 的正整数 M，随后 M 行，每行给出一位人士的身份证号。题目保证身份证号不重复。
3. 输出格式：
首先在第一行输出参加校庆的校友的人数。然后在第二行输出最年长的校友的身份证号 —— 注意身份证第 7-14 位给出的是 yyyymmdd 格式的生日。如果没有校友来，则在第二行输出最年长的来宾的身份证号。题目保证这样的校友或来宾必是唯一的。
4. 输入样例：
5
372928196906118710
610481197806202213
440684198612150417
13072819571002001X
150702193604190912
6
530125197901260019
150702193604190912
220221196701020034
610481197806202213
440684198612150417
370205198709275042
5. 输出样例：
3
150702193604190912
6. 性能要求：
Code Size Limit
16 KB
Time Limit
800 ms
Memory Limit
64 MB
思路：
首先将校友和参加校庆的人的信息分别保存，然后遍历参加校庆的人判断是否为校友，将参加校庆的校友另外进行保存，这里相当于在校友信息中进行搜索，为了减少耗时，首先调用库函数qsort()将校友信息按身份证进行排序，然后调用库函数bsearch()进行二分搜索，最后根据是否有校友参加分情况对相关人员按照生日排序，输出最年长的身份证号。
这里需要特别注意的是排序函数的编写，涉及到二维数组的地址问题，容易出现Segmentation Fault。。。因为对二维数组名解引用得到的是一个一维数组对象，这一点目前搞的也不是很清楚。
My Code:
#include <stdio.h>
#include <stdlib.h> // qsort header, bsearch header, malloc header
#include <string.h> // strcmp header, strcpy header
#define MAX_NUM 100000
int sort_alu(const void *p1, const void *p2);
int sort_bsearch(const void *p1, const void *p2);
int sort_birth(const void *p1, const void *p2);
int main(void)
{
char alumni[MAX_NUM][19] = {""};
char guest[MAX_NUM][19] = {""};
int alumniCount = 0;
int guestCount = 0;
char attendAlu[MAX_NUM][19] = {""};
int aluAttendCount = 0;
scanf("%d", &alumniCount);
for(int i=0; i<alumniCount; ++i)
{
scanf("%s", alumni[i]);
//printf("%s\n", alumni[i]);
}
scanf("%d", &guestCount);
for(int i=0; i<guestCount; ++i)
{
scanf("%s", guest[i]);
//printf("%s\n", guest[i]);
}
//char (*pAlu)[19] = (char (*)[19])malloc(sizeof(char [19]))
char **pAlu = malloc(sizeof(char *) * alumniCount); // allocate heap memory
for(int i=0; i<alumniCount; ++i) // assign the pointer to alumni
{
pAlu[i] = alumni[i];
}
qsort(pAlu, alumniCount, sizeof(char *), sort_alu); // sort alumni by ID
// for(int i=0; i<alumniCount; ++i) // output sort result
// {
// printf("%s\n", pAlu[i]);
// }
for(int i=0; i<guestCount; ++i)
{
//void *bsearch(const void *key, const void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *))
// bsearch have bug
if(bsearch(guest[i], pAlu, alumniCount, sizeof(char *), sort_bsearch)) // this guest is alumni
{
strcpy(attendAlu[aluAttendCount++], guest[i]);
}
}
// for(int i=0; i<aluAttendCount; ++i) // output attendAlu info
// {
// printf("%s\n", attendAlu[i]);
// }
printf("%d\n", aluAttendCount);
if(aluAttendCount) // have alumni attend party
{
char **pRes = malloc(sizeof(char *) * aluAttendCount); // allocate heap memory
for(int i=0; i<aluAttendCount; ++i)
{
pRes[i] = attendAlu[i];
}
qsort(pRes, aluAttendCount, sizeof(char *), sort_birth); // sort by birth
//qsort(attendAlu, aluAttendCount, sizeof(char *), sort_birth); // sort by birth
printf("%s\n", pRes[0]);
// for(int i=0; i<aluAttendCount; ++i) // output attendAlu info
// {
// printf("%s\n", attendAlu[i]);
// }
free(pRes);
}
else // doesn't have alumni attend party
{
char **pRes = malloc(sizeof(char *) * guestCount); // allocate heap memory
for(int i=0; i<guestCount; ++i)
{
pRes[i] = guest[i];
}
qsort(pRes, guestCount, sizeof(char *), sort_birth); // sort by birth
printf("%s\n", pRes[0]);
free(pRes);
}
free(pAlu); // release heap memory
return 0;
}
int sort_alu(const void *p1, const void *p2)
{
// char (*pLeft)[19] = (char (*)[19])(*(char **)p1);
// char (*pRight)[19] = (char (*)[19])(*(char **)p2);
char (*pLeft)[19] = (*(char **)p1);
char (*pRight)[19] = (*(char **)p2);
return (strcmp(pLeft, pRight));
}
int sort_bsearch(const void *p1, const void *p2)
{
// char (*pValue)[19] = (*(char **)p1); // this will cause segmentation fault
// char (*pElem)[19] = (*(char **)p2);
char *pValue = (char *)p1;
char *pElem = *(char **)p2;
return (strcmp(pValue, pElem));
}
int sort_birth(const void *p1, const void *p2)
{
char *pLeft = *(char **)p1;
char *pRight = *(char **)p2;
return strcmp(pLeft+6, pRight+6);
}