1095 解码PAT准考证 （25分）击破测试点3、4，50ms内通关
1095 解码PAT准考证 （25分）测试点34用时低于35ms
- 前言
- 一、题目简介
- 二、原题内容
- 1. 设定
- 2. 输入格式
- 3. 输出格式
- 三、题目分析
- 1. 要求1分析
- 2. 要求2分析
- 3. 要求3分析
- 4. 完整代码
- 总结
前言
肝了四五天，肝完了PAT乙级真题。1095 解码PAT准考证 （25分）作为PAT乙级的最后一道题，题目的复杂程度相较前面的题目有所提升，对时间的把控要求也更高，基本上代表了乙级真题里的最高难度，属于毕业题。如果采用复杂冗长的代码和非缓存式的计算结构，很有可能使得此题的最后两个测试点因为超时而无法通过。附上本文代码，平均用时，测试点3、4用时30-50ms以内，测试点0、1用时5ms上下，测试点2用时14ms上下。
提示：以下是本篇文章正文内容，下面案例可供参考
一、题目简介
给定准考证号及考试成绩。
要求1：根据级别，输出准考证号和分数。(输出多行）
要求2：根据考场号，输出人数和总分.（输出单行）
要求3：根据日期，输出考场号和总人数.（输出多行）
二、原题内容
1. 设定
PAT 准考证号由 4 部分组成：
- 第 1 位是级别，即 T 代表顶级；A 代表甲级；B 代表乙级；
- 第 2~4 位是考场编号，范围从 101 到 999；
- 第 5~10位是考试日期，格式为年、月、日顺次各占 2 位；
- 最后 11~13 位是考生编号，范围从 000 到 999。
现给定一系列考生的准考证号和他们的成绩，请你按照要求输出各种统计信息。
2. 输入格式
输入首先在一行中给出两个正整数 N（≤10000 ）和 M（≤100），分别为考生人数和统计要求的个数。
接下来 N 行，每行给出一个考生的准考证号和其分数（在区间 [0,100] 内的整数），其间以空格分隔。
考生信息之后，再给出 M 行，每行给出一个统计要求，格式为：类型 指令，其中
- 类型 为 1 表示要求按分数非升序输出某个指定级别的考生的成绩，对应的 指令 则给出代表指定级别的字母；
- 类型 为 2 表示要求将某指定考场的考生人数和总分统计输出，对应的 指令 则给出指定考场的编号；
- 类型 为 3 表示要求将某指定日期的考生人数分考场统计输出，对应的 指令 则给出指定日期，格式与准考证上日期相同。
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三、题目分析
1. 要求1分析
类型 为 1 表示要求按分数非升序输出某个指定级别的考生的成绩，对应的 指令 则给出代表指定级别的字母；
即：给定级别（ID[0]），输出排序后的编号（ID）和得分（score）
定义。给定结构体：
定义。给定排序方法：
int cmp(Info a, Info b) {return a.score == b.score ? a.id < b.id : a.score > b.score; }处理输入。
使用数组存储各个级别对应的个人信息结构体。‘A’, ‘B’, 'T’各自对应一组结构体集合。由于map的特性，如果没有对应的级别，也不会额外创建这组结构体。
特别说明的是，只有case1需要提前全部计算完毕三种组合，以便于查询过程中随用随取。其余Case2，Case3，输入对应的所有组合数量多，如果提前全部计算，查询数目远远小于计算的数目，会导致大量不必要的开销。
处理输出。map类型的mci.count(char)==1意义是判断该关键字是否在字典中出现过，相当于mci.find(char)!=mci.end()。
case 1: {scanf("%c", &c);printf("Case %d: %d %c\n", i + 1, choice, c);if (mci.count(c)==1) {for (int i = 0; i < mci[c].size(); i++) {cout << mci[c][i].id;printf(" %d\n", mci[c][i].score);}}else {printf("NA\n");}break;}2. 要求2分析
- 类型 为 2 表示要求将某指定考场的考生人数和总分统计输出，对应的 指令 则给出指定考场的编号；
即：给定考场号（ID[1-3]），输出该考场号对应的总人数（num）和总得分（score）。
定义。给定结构体：
如果没有缓存处理，代码是如下结构：
case 2: {cin >> placeId;printf("Case %d: %d ", i + 1, choice);cout << placeId << endl;score = num = 0;for(int i = 0; i < N; i++){if (vInfo[i].id.substr(1, 3) == placeId) {num++;score += vInfo[i].score;}}if (num > 0) {printf("%d %d\n", num, score);}else printf("NA\n");break;}这一串代码很简洁，把要处理的任务都处理掉了。每次查询都会遍历一遍所有考生的信息，检查N个考生的考场号是否与待查询的考场号相符。
但是这样做问题很明显：如果接下来100条查询都和第一次的查询一样，都在查询某一个场次，则会访问100*N次，时间复杂度为O(MN)。而如果将第一次查询的结果保存在一个字典中，下一次查询时候就可以直接读出，访问次数为N+100次，时间复杂度降为O(M+N)。
每次查询时，首先看该记录是否已经被缓存，如果已经被缓存，则访问并退出；否则，逐个检查N个考生的考场号，并将结果进行缓存。缓存后的代码如下。
3. 要求3分析
类型 为 3 表示要求将某指定日期的考生人数分考场统计输出，对应的 指令 则给出指定日期，格式与准考证上日期相同。
即：给定日期（ID[4-9]），输出排序后的考场号（ID[1-3]）和总人数（num）
复用前文的结构体，因为要求3的输出内容也是一个string和int：
如果没有缓存处理，代码是如下结构：
case 3: {cin >> date;printf("Case %d: %d ", i + 1, choice);cout << date << endl;//mp用于存放给定日期下，考场编号到该考场考生人数的映射。map<string, int> mp;//逐个比对日期信息for (int i = 0; i < N; i++) {//日期信息相符if (vInfo[i].id.substr(4, 6) == date) {placeId = vInfo[i].id.substr(1, 3);//计算当日每个考场内的学生总数。if (mp.count(placeId)) {mp[placeId]++;}else {mp[placeId] = 1;}}}//当日没有分配考场if (mp.size() == 0) {printf("NA\n");break;}//只有形成了结构体的向量（数组），才能方便进行排序vector<Info> dp;Info temp;for (map<string, int>::iterator it = mp.begin(); it != mp.end(); it++) {//ID：考场编号。score:该考场内的考生temp.id = it->first;temp.score = it->second;dp.push_back(temp);}//排序sort(dp.begin(), dp.end(), cmp);for (int i = 0; i < dp.size(); i++) {cout << dp[i].id;printf(" %d\n", dp[i].score);}break;}同理，是否采用缓存结构，也是数量级O(MN)到数量级O(M+N)的转换。已经在必要的步骤处做了注释。与上段代码增加的地方就是缓冲的内容。
case 3: {cin >> date;printf("Case %d: %d ", i + 1, choice);cout << date << endl;if (mp3.count(date)) {if (mp3[date].size() == 0) {printf("NA\n");break;}for (int i = 0; i < mp3[date].size(); i++) {cout << mp3[date][i].id;printf(" %d\n", mp3[date][i].score);}break;}//mp用于存放给定日期下，考场编号到该考场考生人数的映射。map<string, int> mp;//逐个比对日期信息for (int i = 0; i < N; i++) {//日期信息相符if (vInfo[i].id.substr(4, 6) == date) {placeId = vInfo[i].id.substr(1, 3);//计算当日每个考场内的学生总数。if (mp.count(placeId)) {mp[placeId]++;}else {mp[placeId] = 1;}}}//当日没有分配考场if (mp.size() == 0) {printf("NA\n");vector<Info> dp;mp3[date] = dp;break;}//只有形成了结构体的向量（数组），才能方便进行排序vector<Info> dp;Info temp;for (map<string, int>::iterator it = mp.begin(); it != mp.end(); it++) {//ID：考场编号。score:该考场内的考生总数。temp.id = it->first;temp.score = it->second;dp.push_back(temp);}//排序sort(dp.begin(), dp.end(), cmp);for (int i = 0; i < dp.size(); i++) {cout << dp[i].id;printf(" %d\n", dp[i].score);}mp3[date] = dp;break;}4. 完整代码
// 创作By:zhangwenniu@163.com，转载请注明出处。#include <string> #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; const int maxn = 10010; struct Info {string id;int score; }; int cmp(Info a, Info b) {return a.score == b.score ? a.id < b.id : a.score > b.score; } struct case2 {int num, score; }; int main() {int N, M, score, num;string id;scanf("%d%d", &N, &M);vector<Info> vInfo;map<char, vector<Info> >mci;for (int i = 0; i < N; i++) {Info info;cin >> info.id;scanf("%d", &info.score);vInfo.push_back(info);mci[info.id[0]].push_back(info);}for (map<char, vector<Info> >::iterator it = mci.begin(); it != mci.end(); it++) {sort(mci[it->first].begin(), mci[it->first].end(), cmp);}int choice;char c, space;string placeId;string date;string others;map<string, case2> mp2;map<string, vector<Info> > mp3;for (int i = 0; i < M; i++) {scanf("%d%c", &choice, &space);switch (choice) {case 1: {scanf("%c", &c);printf("Case %d: %d %c\n", i + 1, choice, c);if (mci.count(c)==1) {for (int i = 0; i < mci[c].size(); i++) {cout << mci[c][i].id;printf(" %d\n", mci[c][i].score);}}else {printf("NA\n");}break;}case 2: {cin >> placeId;printf("Case %d: %d ", i + 1, choice);cout << placeId << endl;if (mp2.count(placeId)) {printf("%d %d\n", mp2[placeId].num, mp2[placeId].score);break;}score = num = 0;for(int i = 0; i < N; i++){if (vInfo[i].id.substr(1, 3) == placeId) {num++;score += vInfo[i].score;}}if (num > 0) {printf("%d %d\n", num, score);case2 cs;cs.num = num;cs.score = score;mp2[placeId] = cs;}else printf("NA\n");break;}case 3: {cin >> date;printf("Case %d: %d ", i + 1, choice);cout << date << endl;if (mp3.count(date)) {if (mp3[date].size() == 0) {printf("NA\n");break;}for (int i = 0; i < mp3[date].size(); i++) {cout << mp3[date][i].id;printf(" %d\n", mp3[date][i].score);}break;}//mp用于存放给定日期下，考场编号到该考场考生人数的映射。map<string, int> mp;//逐个比对日期信息for (int i = 0; i < N; i++) {//日期信息相符if (vInfo[i].id.substr(4, 6) == date) {placeId = vInfo[i].id.substr(1, 3);//计算当日每个考场内的学生总数。if (mp.count(placeId)) {mp[placeId]++;}else {mp[placeId] = 1;}}}//当日没有分配考场if (mp.size() == 0) {printf("NA\n");vector<Info> dp;mp3[date] = dp;break;}//只有形成了结构体的向量（数组），才能方便进行排序vector<Info> dp;Info temp;for (map<string, int>::iterator it = mp.begin(); it != mp.end(); it++) {//ID：考场编号。score:该考场内的考生总数。temp.id = it->first;temp.score = it->second;dp.push_back(temp);}//排序sort(dp.begin(), dp.end(), cmp);for (int i = 0; i < dp.size(); i++) {cout << dp[i].id;printf(" %d\n", dp[i].score);}mp3[date] = dp;break;}default: {getline(cin, others);printf("Case %d: %d ", i + 1, choice);cout << others << endl;printf("NA\n");}}} }总结
提示：注意第三问，要求在给定日期下的某考场，相当于是日期+考场（ID[1-9]）作为总关键字进行统计。当心陷阱。以上就是今天要讲的内容，本文仅仅简单介绍了缓冲思想的应用。最后放上AC的截图，仅供大家参考。
总结
以上是生活随笔为你收集整理的1095 解码PAT准考证 （25分）击破测试点3、4，50ms内通关的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： FZU 2282 错排
- 下一篇： 怎么培养自己的自信心