PAT (Basic Level) Practice-1095 examination permit for decoding PAT
subject
PAT admission number consists of 4 parts:
The first is the level, that is, T stands for the top level; A stands for class A; B stands for class B;
The 2nd to 4th digits are the examination room number, ranging from 101 to 999;
The 5th to 10th places are the examination date, and the format is year, month and day, accounting for 2 places in sequence;
The last 11 ~ 13 digits are the candidate number, ranging from 000 to 999.
A series of examinees' admission numbers and their scores are given. Please output various statistical information as required.
input
Input: first, two positive integers N (≤ 104) and M (≤ 100) are given in one line, which are the number of candidates and the number of statistical requirements respectively.
Next, N lines, each of which gives an examinee's admission number and its score (an integer in the interval [0100]), separated by spaces.
After the candidate information, M lines are given, and each line gives a statistical requirement. The format is: type instruction, where
Type 1 indicates that the scores of candidates at a specified level are required to be output in non ascending order of scores, and the corresponding instructions give letters representing the specified level;
Type 2 indicates that it is required to output the statistics of the number and total score of candidates in a designated examination room, and the corresponding instruction will give the number of the designated examination room;
Type 3 means that the number of candidates on a specified date is required to be output by examination room, and the corresponding instruction gives the specified date in the same format as the date on the admission ticket.
output
For each statistical requirement, first output Case #: requirement in one line, where # is the number of the requirement, starting from 1; The requirement is to copy the requirement given by the input. Then output the corresponding statistical results:
For the instruction of type 1, the output format is the same as the input examinee information format, that is, the admission ticket number and score. For examinees with parallel scores, output them incrementally according to the dictionary order of their admission number (the title shall ensure that there is no duplicate admission number);
Instructions of type 2 are output in the format of total score of the number of people;
For the instruction of type 3, the output is in the non increasing order of the number of people, and the format is the total number of people in the examination room number. If the number of people is in parallel, it will be output in ascending order according to the examination room number.
If the query result is empty, NA is output.
thinking
Note that the time limit of this topic is 200ms, so the complexity of the algorithm should not be too high. Each type only uses one layer of for loop
For each instruction, try to sort all information according to requirements before screening
Type 1 first arranges all candidates in non ascending order of scores, and then traverses the sorted array
Type 2 can be directly traversed and counted
Use map for type 3, otherwise timeout is required
Finally, all output is printed in printf (printf is faster than cout)
Final code
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
struct kaosheng {
string id;
int score;
};
struct Date {
int kc;
int totalr = 0;
};
vector<kaosheng> pat;
int getkc(string s) {
int kc = 0;
for (int j = 1; j < 4; j++)
kc = kc * 10 + s[j] - '0';
return kc;
}
bool cmp1(kaosheng a, kaosheng b) {
if (a.score != b.score)
return a.score > b.score;
else
return a.id < b.id;
}
bool cmp2(Date a, Date b) {
if (a.totalr != b.totalr)
return a.totalr > b.totalr;
else
return a.kc < b.kc;
}
int tongji(int n) {
//cout << n << ' ';
printf("%d ", n);
switch (n) {
case 1: {
char j;
cin >> j;
//cout << j << endl;
printf("%c\n", j);
int flag = 0;
sort(pat.begin(), pat.end(), cmp1);
for (int i = 0; i < pat.size(); i++) {
if (pat[i].id[0] == j) {
//cout << pat[i].id << ' ' << pat[i].score << endl;
printf("%s %d\n", pat[i].id.c_str(), pat[i].score);
flag = 1;
}
}
if (!flag) //cout << "NA" << endl;
printf("NA\n");
break; }
case 2: {
int kaochang, totalr, totals;
totalr = 0; totals = 0;
cin >> kaochang;
//cout << kaochang << endl;
printf("%d\n", kaochang);
for (int i = 0; i < pat.size(); i++) {
int kc = getkc(pat[i].id);
if (kc == kaochang) {
totalr++;
totals += pat[i].score;
}
}
if (totalr == 0) //cout << "NA" << endl;
printf("NA\n");
else //cout << totalr << ' ' << totals << endl;
printf("%d %d\n", totalr, totals);
break; }
case 3: {
vector<Date> datee;
int n = 0;
map<int, int> datem;
string date;
cin >> date;
cout << date << endl;
for (int i = 0; i < pat.size(); i++) {
if (pat[i].id.substr(4, 6) != date) continue;
int kc = getkc(pat[i].id);
if (datem.find(kc) == datem.end()) {
datem[kc] = n;
n++;
datee.push_back({ kc,1 });
}
else {
datee[datem[kc]].totalr++;
}
}
if (datee.size() == 0) cout << "NA" << endl;
else {
sort(datee.begin(), datee.end(), cmp2);
for (int j = 0; j < datee.size(); j++)
//cout << datee[j].kc<< ' ' << datee[j].totalr << endl;
printf("%d %d\n", datee[j].kc, datee[j].totalr);
}
break; }
default:
//cout << "NA" << endl;
printf("NA\n");
break;
return 0;
}
}
int main() {
int N, M;
cin >> N >> M;
for (int i = 0; i < N; i++) {
string id;
int score;
cin >> id >> score;
pat.push_back({ id,score });
}
for (int i = 0; i < M; i++) {
//cout << "Case " << i + 1 << ": ";
printf("Case %d: ", i + 1);
int type;
cin >> type;
tongji(type);
}
return 0;
}
Problems encountered
-
overtime
The time complexity is too large. It doesn't use the map. It takes two layers to time out -
Or timeout
cout is used for output
summary
To save time:
- Sort first and then traverse
- Use map
- Change the input to printf