乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT (Basic Level) Practice 1100 校庆

问题分析

• 题设给定了一组校友ID, 然后给定了一组来宾ID, 要求输出是校友的来宾中, 最年长的一位。
• 如果来宾中没有校友, 则输出来宾中最年长的一位。
• 由于涉及到查询, 所以本题的重点在于数据的存储与查询。ID是由数字和大写字母组成, 所以需要存储成字符串。
• 查询时的比较可以使用字符串比较函数。
• 同时为了性能考虑, 可能先对要查询的校友ID进行排序, 然后查询时使用二分查找。
• 进一步性能考虑, 存储最值时可以存储最年长校友在数组中的索引而不是直接存储字符串, 避免多次字符串拷贝。

完整描述步骤

1. 获取输入: 校友人数, 各个校友的ID
2. 对各个校友的ID进行排序
3. 初始化记录器:
   • 最年长的校友索引 = -1
   • 最年长的来宾索引 = -1
   • 最年长的校友生日 = “99999999”
   • 最年长的来宾生日 = “99999999”
   • 出席的来宾是校友的数量 = 0
4. 获取输入: 来宾人数, 各个来宾的ID
5. 对于每一个来宾的ID:
   • 如果来宾的ID在校友ID中:
     • 出席的来宾是校友的数量++
     • 如果来宾的生日 大于 最年长的校友生日:
       • 最年长的校友生日 = 来宾生日
       • 最年长的校友索引 = 当前来宾索引
   • 否则:
     • 如果来宾的生日 大于 最年长的来宾生日:
       • 最年长的来宾生日 = 来宾生日
       • 最年长的来宾索引 = 当前来宾索引
6. 输出 出席的来宾是校友的数量
7. 如果 出席的来宾是校友的数量 > 0:
   • 输出 来宾IDs[最年长的校友索引]
8. 否则:
   • 输出 来宾IDs[最年长的来宾索引]

伪代码描述

1. get input: schoolmate_amount, schoolmate_IDs
2. sort schoolmate_IDs
3. get input: guest_amount, guest_IDs
4. init recorder:
   • eldest_schoolmate_birthday = “99999999”;
   • eldest_schoolmate_index = -1;
   • eldest_guest_birthday = “99999999”;
   • eldest_guest_index = -1;
   • schoolmate_guest_amount = 0;
5. for index, guest_ID in guest_IDs:
   • guest_birthday = guest_ID[6:14];
   • if guest_ID in schoolmate_IDs:
     • schoolmate_guest_amount++;
     • if birthday < eldest_schoolmate_birthday:
       • eldest_schoolmate_birthday = birthday;
       • eldest_schoolmate_index = index;
   • else:
     • if birthday < eldest_guest_birthday:
       • eldest_guest_birthday = birthday;
       • eldest_guest_index = index;
6. print(schoolmate_guest_amount);
7. if schoolmate_guest_amount > 0:
   • print(guest_IDs[eldest_schoolmate_index]);
8. else:
   • print(guest_IDs[eldest_guest_index]);

注意事项

1. 测试点1, 测试点4错误
   • 由于不管是最年长的校友还是来宾, 记录的索引都是来宾数组中的索引
   • 所以输出的时候也要从来宾数组中获取

完整提交代码

/*
# 问题分析
题设给定了一组校友ID, 然后给定了一组来宾ID, 要求输出是校友的来宾中, 最年长的一位。
如果来宾中没有校友, 则输出来宾中最年长的一位。
由于涉及到查询, 所以本题的重点在于数据的存储与查询。ID是由数字和大写字母组成, 所以需要存储成字符串。
查询时的比较可以使用字符串比较函数。
同时为了性能考虑, 可能先对要查询的校友ID进行排序, 然后查询时使用二分查找。
进一步性能考虑, 存储最值时可以存储最年长校友在数组中的索引而不是直接存储字符串, 避免多次字符串拷贝。# 完整描述步骤
1. 获取输入: 校友人数, 各个校友的ID
2. 对各个校友的ID进行排序
3. 初始化记录器:- 最年长的校友索引 = -1- 最年长的来宾索引 = -1- 最年长的校友生日 = "99999999"- 最年长的来宾生日 = "99999999"- 出席的来宾是校友的数量 = 0
4. 获取输入: 来宾人数, 各个来宾的ID
5. 对于每一个来宾的ID:- 如果来宾的ID在校友ID中:- 出席的来宾是校友的数量++- 如果来宾的生日 大于 最年长的校友生日:- 最年长的校友生日 = 来宾生日- 最年长的校友索引 = 当前来宾索引- 否则:- 如果来宾的生日 大于 最年长的来宾生日:- 最年长的来宾生日 = 来宾生日- 最年长的来宾索引 = 当前来宾索引
6. 输出 出席的来宾是校友的数量
7. 如果 出席的来宾是校友的数量 > 0:- 输出 来宾IDs[最年长的校友索引]
8. 否则:- 输出 来宾IDs[最年长的来宾索引]# 伪代码描述
1. get input: schoolmate_amount, schoolmate_IDs
2. sort schoolmate_IDs
3. get input: guest_amount, guest_IDs
4. init recorder:- eldest_schoolmate_birthday = "99999999";- eldest_schoolmate_index = -1;- eldest_guest_birthday = "99999999";- eldest_guest_index = -1;- schoolmate_guest_amount = 0;
5. for index, guest_ID in guest_IDs:- guest_birthday = guest_ID[6:14];- if guest_ID in schoolmate_IDs:- schoolmate_guest_amount++;- if birthday < eldest_schoolmate_birthday:- eldest_schoolmate_birthday = birthday;- eldest_schoolmate_index = index;- else:- if birthday < eldest_guest_birthday:- eldest_guest_birthday = birthday;- eldest_guest_index = index;
6. print(schoolmate_guest_amount);
7. if schoolmate_guest_amount > 0:- print(guest_IDs[eldest_schoolmate_index]);
8. else:- print(guest_IDs[eldest_guest_index]);# 注意事项
1. 测试点1, 测试点4错误- 由于不管是最年长的校友还是来宾, 记录的索引都是来宾数组中的索引- 所以输出的时候也要从来宾数组中获取
*/# include
# include
# includechar schoolmate_IDs[100000][19];
char guest_IDs[100000][19];int cmp_ID(const void* a, const void* b){return strcmp((char*) a, (char*) b);
}void extract_birthday_from_ID(char *birthday, char *ID){for (int i = 0; i < 8; i++){birthday[i] = ID[i+6];}birthday[8] = '\0';
}int main(){int schoolmate_amount;scanf("%d", &schoolmate_amount);for (int i = 0; i < schoolmate_amount; i++){scanf("%s", schoolmate_IDs[i]);}qsort(schoolmate_IDs, schoolmate_amount, sizeof(char)*19, cmp_ID);int guest_amount;scanf("%d", &guest_amount);for (int i = 0; i < guest_amount; i++){scanf("%s", guest_IDs[i]);}char eldest_schoolmate_birthday[9] = "99999999";int eldest_schoolmate_index = -1;char eldest_guest_birthday[9] = "99999999";int eldest_guest_index = -1;char schoolmate_guest_amount = 0;char birthday[9];for (int i = 0; i < guest_amount; i++){extract_birthday_from_ID(birthday, guest_IDs[i]);char **found = bsearch(guest_IDs[i], schoolmate_IDs, schoolmate_amount, sizeof(char)*19, cmp_ID);if (found != NULL){schoolmate_guest_amount++;if (strcmp(birthday, eldest_schoolmate_birthday) < 0){strcpy(eldest_schoolmate_birthday, birthday);eldest_schoolmate_index = i;}}if (strcmp(birthday, eldest_guest_birthday) < 0) {strcpy(eldest_guest_birthday, birthday);eldest_guest_index = i;}}printf("%d\n", schoolmate_guest_amount);if (schoolmate_guest_amount > 0){printf("%s\n", guest_IDs[eldest_schoolmate_index]);} else {printf("%s\n", guest_IDs[eldest_guest_index]);}return 0;
}