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 错排
- 下一篇： C++ 推箱子，中配版，支持玩家自己创造