http://pat.zju.edu.cn/contests/pat-a-practise/1022
PAT1022 这道题目就是一个查找题目，给你一本书id,作者，关键字，年份，出版商。然后会给出某一些查询请求，主要是查询时间的考虑。我估计出题者主要是想考察有序插入排序和二分查找这两个过程。考虑一下最大数据量10^4,查询次数10^3，关键字10^3，那么如果线性查找所有关键字，那么将会达到10^10操作，淂超出1000ms。需要用排序加上二分查找，关键字就可以在n*logn时间内完成。
我的思路是用title_dir来记录string-->id的记录，在title[0]记录下表0对应的id,在title[1]记录下表1对应的id。类型是vector<string>。
刚开始我用vecotor<pair<string,int>>记录关键字，但是由于vector在插入的时候无法保证有序插入，当让你可以自己实现了，但是会比较麻烦。然后在用二分查找关键字，然后返回这个关键字对应的下标。
map是用红黑树来保存所有数据结构的，所以查找效率可以达到logn。所以Map的查很效率是很高的。所以log10^10之后会低于要求的时间。
0 答案正确 2 1524 16/16 1 答案正确 2 1532 3/3 2 答案正确 2 1528 3/3 3 答案正确 2 1528 3/3 4 答案正确 127 6516 5/5
可以看到最后一个大数据话费127ms。10^9大约是1s,log10^10/10^9=??(right？)
#include<stdio.h> #include<string> #include<algorithm> #include<vector> #include<map> #include<iostream> using namespace std; #define MAX 10010 struct Pair { Pair(string a,int ind) { id=a; index=ind; } bool operator<(const Pair & y) const { if(id<y.id) return true; return false; } string id; int index; }; // //vector<Pair> title_dir; //vector<Pair> author_dir; //vector<Pair> keyword_dir; //vector<Pair> publish_dir; //vector<Pair> year_dir; map<string,int> title_dir; map<string,int> author_dir; map<string,int> keyword_dir; map<string,int> publish_dir; map<string,int> year_dir; vector<string> title[MAX]; vector<string> author[MAX]; vector<string> keyword[MAX]; vector<string> publish[MAX]; vector<string> year[MAX]; int getLen(int index) { int len=0; switch(index) { case 1: len=title_dir.size(); break; case 2: len=author_dir.size(); break; case 3: len=keyword_dir.size(); break; case 4: len=publish_dir.size(); break; case 5: len=year_dir.size(); break; } return len; } int findIndex(int index,string key)//find index of key { map<string,int>::iterator it; int l,r,mid; int pos=-1; switch(index) { case 1: it=title_dir.find(key); if(it!=title_dir.end()) pos=it->second; break; case 2: it=author_dir.find(key); if(it!=author_dir.end()) pos=it->second; break; case 3: it=keyword_dir.find(key); if(it!=keyword_dir.end()) pos=it->second; break; case 4: it=publish_dir.find(key); if(it!=publish_dir.end()) pos=it->second; break; case 5: it=year_dir.find(key); if(it!=year_dir.end()) pos=it->second; break; } return pos; } int main() { freopen("1022-in.txt","r",stdin); freopen("1022-out.txt","w",stdout); string id,tit,auth,key,pub,ye; int n; cin>>n; getchar(); for(int i=0;i<n;i++) { getline(cin,id); getline(cin,tit); getline(cin,auth); getline(cin,key); getline(cin,pub); getline(cin,ye); int index; int len; index=findIndex(1,tit); if(index==-1)//notfind { len=getLen(1); index=len; title_dir.insert(make_pair(tit,index)); } title[index].push_back(id); index=findIndex(2,auth); if(index==-1)//notfind { len=getLen(2); index=len; //author_dir.push_back(Pair(auth,index)); author_dir.insert(make_pair(auth,index)); } author[index].push_back(id); index=findIndex(4,pub); if(index==-1)//notfind { len=getLen(4); index=len; //publish_dir.push_back(Pair(pub,index)); publish_dir.insert(make_pair(pub,index)); } publish[index].push_back(id); index=findIndex(5,ye); if(index==-1)//notfind { len=getLen(5); index=len; //year_dir.push_back(Pair(ye,index)); year_dir.insert(make_pair(ye,index)); } year[index].push_back(id); int begin=0; int ke_len=key.length(); for(int j=0;j<ke_len;j++) { if(key[j]==' ') { string tmp=key.substr(begin,j-begin); index=findIndex(3,tmp); if(index==-1)//notfind { len=getLen(3); index=len; //keyword_dir.push_back(Pair(tmp,index)); keyword_dir.insert(make_pair(tmp,index)); } keyword[index].push_back(id); begin=j+1; } } string tmp=key.substr(begin,ke_len-begin); index=findIndex(3,tmp); if(index==-1)//notfind { len=getLen(3); index=len; keyword_dir.insert(make_pair(tmp,index)); } keyword[index].push_back(id); } //sort vector for(int j=0;j<title_dir.size();j++) { sort(title[j].begin(),title[j].end()); } for(int j=0;j<author_dir.size();j++) { sort(author[j].begin(),author[j].end()); } for(int j=0;j<keyword_dir.size();j++) { sort(keyword[j].begin(),keyword[j].end()); } for(int j=0;j<publish_dir.size();j++) { sort(publish[j].begin(),publish[j].end()); } for(int j=0;j<year_dir.size();j++) { sort(year[j].begin(),year[j].end()); } int m; string type; string value; cin>>m; int index=-1; vector<string>::iterator it; for(int j=0;j<m;j++) { cin>>type; getchar(); getline(cin,value); cout<<type<<" "<<value<<endl; switch(type[0]-'0') { case 1: index=findIndex(1,value); if(index==-1) { cout<<"Not Found"<<endl; break; } it=title[index].begin(); for(;it!=title[index].end();it++) { cout<<*it<<endl; } break; case 2: index=findIndex(2,value); if(index==-1) { cout<<"Not Found"<<endl; break; } it=author[index].begin(); for(;it!=author[index].end();it++) { cout<<*it<<endl; } break; case 3: index=findIndex(3,value); if(index==-1) { cout<<"Not Found"<<endl; break; } it=keyword[index].begin(); for(;it!=keyword[index].end();it++) { cout<<*it<<endl; } break; case 4: index=findIndex(4,value); if(index==-1) { cout<<"Not Found"<<endl; break; } it=publish[index].begin(); for(;it!=publish[index].end();it++) { cout<<*it<<endl; } break; case 5: index=findIndex(5,value); if(index==-1) { cout<<"Not Found"<<endl; break; } it=year[index].begin(); for(;it!=year[index].end();it++) { cout<<*it<<endl; } break; } } return 0; }