首先是鬼鬼珊的闲聊一分钟 在之前的博客里，如果你看过的话，一定知道我肯定每天一问，什么时候甜甜的恋爱才能轮到我呀？哈哈哈，然后呢，现在真的轮到我了。是的，超级无敌酷的鬼鬼珊同学真的谈恋爱了，暂时还不知道甜不甜，体会还不深，以后体会深刻的话，一定在博客里认真仔细的写下来。（话就先放在这里，以后肯定写篇博客关于恋爱甜不甜的感受进行深刻的剖析），说一下我的感受吧，大概是第一次谈恋爱的原因，总觉得很恍惚，很不真实，诶，我真的有了男朋友啦？？？最近博主很倒霉，把脚崴了，第一次肿成了猪蹄，以前生病自己都是一个人去看病，早已练就了一身无坚不摧的身心，哈哈哈，略显夸张。但这次真的感受到有男朋友后的不一样体验呢。打住，这不是一篇秀恩爱的博客，这是一篇关于学习的博客，博主的梦想是靠着学习涨粉呢。。。。 言归正传
A registration card number of PAT consists of 4 parts:
the 1st letter represents the test level, namely, T for the top level, A for advance and B for basic; the 2nd - 4th digits are the test site number, ranged from 101 to 999; the 5th - 10th digits give the test date, in the form of yymmdd; finally the 11th - 13th digits are the testee’s number, ranged from 000 to 999. Now given a set of registration card numbers and the scores of the card owners, you are supposed to output the various statistics according to the given queries.
Input Specification: Each input file contains one test case. For each case, the first line gives two positive integers N (≤10的4次方 ) and M (≤100), the numbers of cards and the queries, respectively.Then N lines follow, each gives a card number and the owner’s score (integer in [0,100]), separated by a space.After the info of testees, there are M lines, each gives a query in the format Type Term, where Type being 1 means to output all the testees on a given level, in non-increasing order of their scores. The corresponding Term will be the letter which specifies the level; Type being 2 means to output the total number of testees together with their total scores in a given site. The corresponding Term will then be the site number; Type being 3 means to output the total number of testees of every site for a given test date. The corresponding Term will then be the date, given in the same format as in the registration card. Output Specification: For each query, first print in a line Case #: input, where # is the index of the query case, starting from 1; and input is a copy of the corresponding input query. Then output as requested:
for a type 1 query, the output format is the same as in input, that is, CardNumber Score. If there is a tie of the scores, output in increasing alphabetical order of their card numbers (uniqueness of the card numbers is guaranteed); for a type 2 query, output in the format Nt Ns where Nt is the total number of testees and Ns is their total score; for a type 3 query, output in the format Site Nt where Site is the site number and Nt is the total number of testees at Site. The output must be in non-increasing order of Nt’s, or in increasing order of site numbers if there is a tie of Nt. If the result of a query is empty, simply print NA.
Sample Input:
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
Sample Output:
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查询和2查询都比较简单，只是第三步要考虑到时间效率问题。其实这道题还有一个体会就是要领会题目的意思，座位号是101到999的，所以一共只有899个座位，为什么这里要强调，因为第三个查询是要找出该日期下的学号，并且按照座位号进行统计，座位号相同的进行计数，按照数目个数从大到小输出，数目相同，就按照座位号的升序输出。因为座位号只有899个，我在对每一个学号匹配好日期之后，如果是属于该日期下，那么我处理一下座位号，即在相应的座位号进行加一，到时候对座位数组进行排序，时间复杂度就算是899的平方也比10000的平方要小很多。
#include <iostream> #include<bits/stdc++.h> #define MaxSize 900 using namespace std; struct Student { string number; int score; Student(string temp_number,int temp_score):number(temp_number),score(temp_score) {} }; struct Site{ int site; int c_count=0; }; int N,M; vector<Student> studentList[3]; //每一个级别单独存放 Site siteList[MaxSize]; //座位号数组，存放该日期下，该座位号有多少人，结构体的site存放是为了排序的时候便于处理 bool Compare(Student s1,Student s2) { if(s1.score>s2.score||(s1.score==s2.score&&(s1.number.compare(s2.number)<0))) { return true; } return false; } bool Compare_two(Site s1,Site s2){ if(s1.c_count>s2.c_count||(s1.c_count==s2.c_count&&s1.site<s2.site)){ return true; } return false; } int Level(char c) { switch(c) { case 'T': return 0; case 'A': return 1; default: return 2; } } void Input() { string tempString; int temp_score; cin>>N>>M; for(int i=0; i<N; i++) { cin>>tempString>>temp_score; switch(tempString[0]) { case 'T': studentList[0].push_back(Student(tempString,temp_score)); break; case 'A': studentList[1].push_back(Student(tempString,temp_score)); break; default: studentList[2].push_back(Student(tempString,temp_score)); } } } void Process_One(char level) //处理1查询 { int index=Level(level); sort(studentList[index].begin(),studentList[index].end(),Compare); if(studentList[index].size()==0){ cout<<"NA"<<endl; return; } for(int i=0; i<studentList[index].size(); i++) { cout<<studentList[index][i].number<<" "<<studentList[index][i].score<<endl; } } void Process_Two(string site) //处理2查询 { int Nt=0,Ns=0; int index,k; for(int i=0; i<3; i++) { for(int j=0; j<studentList[i].size(); j++) { index=0; for(k=1; k<=3; k++) { if(studentList[i][j].number[k]!=site[index]) { break; } index++; } if(k==4) { Nt++; Ns+=studentList[i][j].score; } } } if(Nt==0){ cout<<"NA"<<endl; } else{ cout<<Nt<<" "<<Ns<<endl; } } void Process_three(string date){ //处理3查询 string str; int temp_site; for(int i=1;i<900;i++){ siteList[i].site=0; siteList[i].c_count=0; } for(int i=0;i<3;i++){ for(int j=0;j<studentList[i].size();j++){ //判断此时的相应位是否日期一致 str=studentList[i][j].number.substr(4,9); str=str.substr(0,6); if(str.compare(date)==0){ temp_site=(studentList[i][j].number[1]-'0')*100+(studentList[i][j].number[2]-'0')*10+studentList[i][j].number[3]-'0'; siteList[temp_site-100].site=temp_site; siteList[temp_site-100].c_count++; } } } sort(siteList+1,siteList+900,Compare_two); if(siteList[1].c_count==0){ cout<<"NA"<<endl; return; } int i=1; while(siteList[i].c_count>0){ cout<<siteList[i].site<<" "<<siteList[i].c_count<<endl; i++; } } int main() { int type; string diagram; Input(); for(int i=1; i<=M; i++) { cin>>type>>diagram; cout<<"Case "<<i<<": "<<type<<" "<<diagram<<endl; switch(type){ case 1:Process_One(diagram[0]);break; case 2:Process_Two(diagram);break; default:Process_three(diagram); } } return 0; }