PAT A1153 Decode Registration Card of PAT　——凭谁问，廉颇老矣，尚能饭否

PAT A1153 Decode Registration Card of PAT

今天选的题目真是*&^%$#*，不但不值钱，搞起来还相当麻烦思路就是输入的过程中根据查询条件映射和排序好所有需要查询的数据。第一个就是PAT分给3个vector去排序；第二个用map(或数组)映射每个site的总分和人数；第三个是map套map映射每个日期中每个site的人数，这个东西因为输出时还要排序，而map仿佛不能用两个维度排序，所以用一个map套vector接过来去排序本来过程就有些曲折，搞第三个时想到map不能按要求排序，一时冲动换成了map套vector，但是因为需要映射，vector只能用下标映射，范围是101~999,所以resize成1000，然后就出事了，后俩测试点一个超时一个超了内存…长这么大超时家常便饭，超内存还是第一次见(我一般比较节俭)。算了半天这些容器，也就map套vector最大，我还上去看了一眼——范围1000，1K * 1K个单元也就8MB而已吧去看了柳婼姐姐的，她是一个个查的也没有超时，不过这样只需要单层map。突然惊醒，又去看了题目，原来N的范围是10000，扩大十倍那我刚好爆了。。。剩下就又是printf大胜利另：时限是200ms,亲测if刚好跑200ms是可以AC的 #include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <math.h> #include <set> #include <map> #include <unordered_map> #include <stack> using namespace std; struct Stu{ string ID; int score; }; struct Res{ string site; int cnt; }; vector<Stu> va,vb,vt; unordered_map<string,int> cnt,total; unordered_map<string,vector<Res> > umap; unordered_map<string,unordered_map<string,int> > umap_tmp; bool cmp(Stu s1,Stu s2){ if(s1.score != s2.score) return s1.score > s2.score; else return s1.ID < s2.ID; } bool cmp1(Res s1,Res s2){ if(s1.cnt != s2.cnt) return s1.cnt > s2.cnt; else return s1.site < s2.site; } #define DEBUG int main(){ #ifdef DEBUG freopen("1.txt","r",stdin); #endif int num,qnum; cin >> num >> qnum; for(int i = 0;i < num;i ++){ Stu s; cin >> s.ID >> s.score; if(s.ID[0] == 'A') va.push_back(s); else if(s.ID[0] == 'B') vb.push_back(s); else vt.push_back(s); string site = s.ID.substr(1,3); if(total[site]) total[site] += s.score; else total[site] = s.score; if(cnt[site]) cnt[site] ++; else cnt[site] = 1; string date = s.ID.substr(4,6); if(umap_tmp[date][site]) umap_tmp[date][site] ++; else umap_tmp[date][site] = 1; //if(umap[date].size() == 0) umap[date].resize(1000); //umap[date][site].site = site; //umap[date][site].cnt ++; } sort(va.begin(),va.end(),cmp); sort(vb.begin(),vb.end(),cmp); sort(vt.begin(),vt.end(),cmp); for(unordered_map<string,unordered_map<string,int> > :: iterator it = umap_tmp.begin();it != umap_tmp.end();it ++){ string date = it -> first; unordered_map<string,int> tmp = it -> second; for(unordered_map<string,int> :: iterator iter = tmp.begin();iter != tmp.end();iter ++){ umap[date].push_back({iter -> first,iter -> second}); } sort(umap[date].begin(),umap[date].end(),cmp1); } /* for(unordered_map<string,vector<Res> > :: iterator it = umap.begin();it != umap.end();it ++){ sort(it -> second.begin(),it -> second.end(),cmp1); } */ for(int i = 0;i < qnum;i ++){ int type; string term; cin >> type >> term; printf("Case %d: %d %s\n",i + 1,type,term.c_str()); //cout << "Case " << i + 1 << ": " << type << ' ' << term << endl; if(type == 1){ vector<Stu> v; if(term[0] == 'A') v = va; else if(term[0] == 'B') v = vb; else v = vt; if(v.size() == 0) printf("NA\n");//cout << "NA\n"; for(int i = 0;i < v.size();i ++) printf("%s %d\n",v[i].ID.c_str(),v[i].score);//cout << v[i].ID << ' ' << v[i].score << endl; }else if(type == 2){ if(cnt[term]) printf("%d %d\n",cnt[term],total[term]);//cout << cnt[term] << ' ' << total[term] << endl; else printf("NA\n");//cout << "NA\n"; }else{ if(umap[term].size()){ vector<Res> v = umap[term]; for(int i = 0;i < v.size();i ++) printf("%s %d\n",v[i].site.c_str(),v[i].cnt);//cout << v[i].site << ' ' << v[i].cnt << endl; }else printf("NA\n");//cout << "NA\n"; } } return 0; }