目录

体会

代码(非满分)

改进

AC代码

体会

这题主要是考察对STL中string,map,vector的应用以及自定义sort()应用。

类型1和2的处理很容易。

类型3要求对于指定date，按照每个考场进行分类，记录不同考场的人数，按照人数非升序，考场号升序(如果前者相同)输出。

我一开始还是很死板地想全在sort里面把它给解决掉，但是一直没做出来。并且收获了map的键和值都不可以是数组的结论。

后面改用这个数据结构

map<int,int> doubleMap[maxn];//map<site,num> doubleMap[date]

map是可以判空、计数和遍历的。而且初始化int值为0，这方便记每个考场的人数。

虽然map不可以排序，但是可以声明和map同样类型的向量vector<int,int>来排序，通过遍历把map的键值拷贝到vector中。遍历的过程中it->first和it->second可以调换位置，虽然本题不这么做也可。

比较函数cmp的参数类型设置为pair<int,int>即可。

以下是类型三相关代码

#part1 
bool cmp3(pair<int,int> a,pair<int,int> b){return a.first!=b.first?a.first>b.first:a.second<b.second; 
}#part2
//type 3
sscanf(str.substr(4,6).c_str(),"%d",&date);	
doubleMap[date][site] ++;#part3
int date;
cin>>date;
printf("Case %d: 3 %d\n",i,date);
if(doubleMap[date].size()==0)printf("NA\n");
else{vector<pair<int,int> > vi;map<int,int>::iterator it = doubleMap[date].begin();for(;it!=doubleMap[date].end();it++){vi.push_back(make_pair(it->second,it->first));}sort(vi.begin(),vi.end(),cmp3);for(int j=0;j<vi.size();j++){printf("%d %d\n",vi[j].second,vi[j].first);}
}

代码(非满分)

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<cstring>
#include<set>using namespace std;const int maxn = 1000001;map<string,int> cardToGrade;map<char,vector<string> > levelToCard;map<int,vector<string> > siteToCard;map<int,int> doubleMap[maxn];//map<site,num> doubleMap[date]bool cmp1(string a,string b){return cardToGrade[a]!=cardToGrade[b]?cardToGrade[a]>cardToGrade[b]:a<b;
}bool cmp3(pair<int,int> a,pair<int,int> b){return a.first!=b.first?a.first>b.first:a.second<b.second; 
}int main(){int pNum,qNum;scanf("%d %d",&pNum,&qNum);string str;int grade,site,date;for(int i=0;i<pNum;i++){	cin>>str;scanf("%d",&grade);cardToGrade[str] = grade;//tyep 1 char level = str[0];levelToCard[level].push_back(str);//type 2sscanf(str.substr(1,3).c_str(),"%d",&site);siteToCard[site].push_back(str);//type 3sscanf(str.substr(4,6).c_str(),"%d",&date);	doubleMap[date][site] ++;}for(int i=1;i<=qNum;i++){int t;cin>>t;switch(t){case 1:char level;cin>>level;printf("Case %d: 1 %c\n",i,level);if(levelToCard[level].size()==0)printf("NA\n");else{sort(levelToCard[level].begin(),levelToCard[level].end(),cmp1);for(int j=0;j<levelToCard[level].size();j++){cout<<levelToCard[level][j]<<" "<<cardToGrade[levelToCard[level][j]]<<endl;}} break;case 2:int site;cin>>site;printf("Case %d: 2 %d\n",i,site);if(siteToCard[site].size()==0)printf("NA\n");else{int nt = siteToCard[site].size();int ns = 0;for(int j=0;j<nt;j++){ns += cardToGrade[siteToCard[site][j]];}cout<<nt<<" "<<ns<<endl;}break;case 3:int date;cin>>date;printf("Case %d: 3 %d\n",i,date);if(doubleMap[date].size()==0)printf("NA\n");else{vector<pair<int,int> > vi;map<int,int>::iterator it = doubleMap[date].begin();for(;it!=doubleMap[date].end();it++){vi.push_back(make_pair(it->second,it->first));}sort(vi.begin(),vi.end(),cmp3);for(int j=0;j<vi.size();j++){printf("%d %d\n",vi[j].second,vi[j].first);}}break;	}}return 0;
}

改进

上述代码提交后还有一个测试用例是错的，一个是超时的

超时解决方案：

用unordered_map取代map（前者在查找时更快）

注意dev本地上可能要加上

#include<tr1/unordered_map>
using namespace std::tr1;

提交时只需要加

#include<unordered_map>

另一改进是，我不再一开始就对输入进行映射分类，而是先存进vector中，再根据需要取所需。

之前可怕的map数组也就变成了普通的map变量

unordered_map<string,int> umap;

另一个小小改进是，把site和date都不看成int而直接视作string，反而遍历了后序的比较。写sscanf不麻烦吗？

AC代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
#include<stdlib.h>
#include<time.h>
#include<vector>
#include<set>
#include<string>
#include<tr1/unordered_map>using namespace std;
using namespace std::tr1;
typedef long long LL;const int maxn = 10007;
const int MOD = 1000000007;
const int INF = 1000000000;//INF:下确界  
const LL SUP = (1LL<<63)-1;//SUP:上确界 
const double eps = 1e-5;struct Node{string id;int v;
};bool cmp1(const Node &a,const Node &b){return a.v!=b.v?a.v>b.v:a.id<b.id;
}bool cmp3(pair<string,int> a,pair<string,int> b){return a.second!=b.second?a.second>b.second:a.first<b.first;
}Node node[maxn];int main(){int pNum,qNum;cin>>pNum>>qNum;for(int i=0;i<pNum;i++){string id;int v;cin>>id>>v;node[i].id = id;node[i].v = v;}for(int i=1;i<=qNum;i++){int t,num = 0,score = 0;vector<Node> vi;string site,date;unordered_map<string,int> umap;vector<pair<string,int> > vi3;cin>>t;switch(t){case 1:char ch;cin>>ch;printf("Case %d: 1 %c\n",i,ch);for(int j=0;j<pNum;j++){if(node[j].id[0]==ch)vi.push_back(node[j]);}if(vi.size()==0)printf("NA\n");else{sort(vi.begin(),vi.end(),cmp1);for(int j=0;j<vi.size();j++){printf("%s %d\n",vi[j].id.c_str(),vi[j].v);}}break;case 2:cin>>site;printf("Case %d: 2 %s\n",i,site.c_str());for(int j=0;j<pNum;j++){if(node[j].id.substr(1,3)==site){num ++;score += node[j].v; }}if(num == 0)printf("NA\n");else printf("%d %d\n",num,score);break;case 3:cin>>date;printf("Case %d: 3 %s\n",i,date.c_str());for(int j=0;j<pNum;j++){if(node[j].id.substr(4,6)==date)umap[node[j].id.substr(1,3)] ++;}if(umap.size()==0)printf("NA\n");else{unordered_map<string,int>::iterator it = umap.begin();for(;it!=umap.end();it++){vi3.push_back(make_pair(it->first,it->second));}sort(vi3.begin(),vi3.end(),cmp3);for(int j=0;j<vi3.size();j++){printf("%s %d\n",vi3[j].first.c_str(),vi3[j].second);}}					}}return 0;
}