Pat1022代码
题目描述：
A Digital Library contains millions of books, stored according to their titles, authors, key words of their abstracts, publishers, and published years. Each book is assigned an unique 7-digit number as its ID. Given any query from a reader, you are supposed to output the resulting books, sorted in increasing order of their ID's.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=10000) which is the total number of books. Then N blocks follow, each contains the information of a book in 6 lines:
- Line #1: the 7-digit ID number;
- Line #2: the book title -- a string of no more than 80 characters;
- Line #3: the author -- a string of no more than 80 characters;
- Line #4: the key words -- each word is a string of no more than 10 characters without any white space, and the keywords are separated by exactly one space;
- Line #5: the publisher -- a string of no more than 80 characters;
- Line #6: the published year -- a 4-digit number which is in the range [1000, 3000].
It is assumed that each book belongs to one author only, and contains no more than 5 key words; there are no more than 1000 distinct key words in total; and there are no more than 1000 distinct publishers.
After the book information, there is a line containing a positive integer M (<=1000) which is the number of user's search queries. Then M lines follow, each in one of the formats shown below:
- 1: a book title
- 2: name of an author
- 3: a key word
- 4: name of a publisher
- 5: a 4-digit number representing the year
Output Specification:
For each query, first print the original query in a line, then output the resulting book ID's in increasing order, each occupying a line. If no book is found, print "Not Found" instead.
Sample Input:31111111The Testing BookYue Chentest code debug sort keywordsZUCS Print20113333333Another Testing BookYue Chentest code sort keywordsZUCS Print220122222222The Testing BookCYLLkeywords debug bookZUCS Print2201161: The Testing Book2: Yue Chen3: keywords4: ZUCS Print5: 20113: blablablaSample Output:
1: The Testing Book111111122222222: Yue Chen111111133333333: keywords1111111222222233333334: ZUCS Print11111115: 2011111111122222223: blablablaNot Found
考虑到用multimap来做，但是相同键值的元素顺序不确定，还要进行一次排序，复杂度与排序算法有关,结果最后一个case运行超时。。。
#include<cstdio>#include<cstdlib>#include<string>#include<iostream>#include<map>#include<vector>#include<algorithm>using namespace std;bool cmp(const string &l,const string &r){ if(l<r) return true; else return false;}int main(int argc,char *argv[]){ int n,m; int i,j; multimap<string,string> title; multimap<string,string> author; multimap<string,string> keyword; multimap<string,string> publisher; multimap<string,string> year; scanf("%d",&n); getchar();//吸收回车符 for(i=0;i<n;i++) { string num,name; string writer,word; string puber,time; getline(cin,num); getline(cin,name); getline(cin,writer); while(1)//截取一个单词 { string word; cin>>word; keyword.insert(pair<string,string>(word,num)); if(getchar()=='\n') break; } getline(cin,puber); getline(cin,time); title.insert(pair<string,string>(name,num)); author.insert(pair<string,string>(writer,num)); publisher.insert(pair<string,string>(puber,num)); year.insert(pair<string,string>(time,num)); } scanf("%d",&m); getchar(); for(i=0;i<m;i++) { int choice; string query; int flag=0; vector<string> v; map<string,string>::iterator it; scanf("%d: ",&choice); getline(cin,query); cout<<choice<<": "<<query<<endl; switch(choice) { case 1: for(it=title.begin();it!=title.end();it++) { if(it->first==query) { flag=1; v.push_back(it->second); } } if(!flag) cout<<"Not Found"<<endl; break; case 2: for(it=author.begin();it!=author.end();it++) { if(it->first==query) { flag=1; v.push_back(it->second); } } if(!flag) cout<<"Not Found"<<endl; break; case 3: for(it=keyword.begin();it!=keyword.end();it++) { if(it->first==query) { flag=1; v.push_back(it->second); } } if(!flag) cout<<"Not Found"<<endl; break; case 4: for(it=publisher.begin();it!=publisher.end();it++) { if(it->first==query) { flag=1; v.push_back(it->second); } } if(!flag) cout<<"Not Found"<<endl; break; case 5: for(it=year.begin();it!=year.end();it++) { if(it->first==query) { flag=1; v.push_back(it->second); } } if(!flag) cout<<"Not Found"<<endl; break; } sort(v.begin(),v.end(),cmp);//键值相等的元素的位置是无序的 vector<string>::iterator iter;//所以要进行排序 for(iter=v.begin();iter!=v.end();iter++) cout<<*iter<<endl; } return 0;}方法二：将map与set结合起来，这样就不用进行排序了，复杂度低于方法一。
AC代码：
#include<cstdio>#include<cstdlib>#include<string>#include<iostream>#include<map>#include<set>#include<algorithm>using namespace std;int main(int argc,char *argv[]){ int n,m; int i,j; map<string,set<string> > title; map<string,set<string> > author; map<string,set<string> > keyword; map<string,set<string> > publisher; map<string,set<string> > year; map<string,set<string> >::iterator it; scanf("%d",&n); getchar(); for(i=0;i<n;i++) { string num,name; string writer,word; string puber,time; getline(cin,num); getline(cin,name); getline(cin,writer); while(1) { string word; cin>>word; keyword[word].insert(num); if(getchar()=='\n') break; } getline(cin,puber); getline(cin,time); title[name].insert(num); author[writer].insert(num); publisher[puber].insert(num); year[time].insert(num); } scanf("%d",&m); getchar(); for(i=0;i<m;i++) { int choice; string query; set<string>::iterator pos; scanf("%d: ",&choice); getline(cin,query); cout<<choice<<": "<<query<<endl; switch(choice) { case 1: it=title.find(query); if(it==title.end()) cout<<"Not Found"<<endl; else { for(pos=it->second.begin();pos!=it->second.end();pos++) cout<<*pos<<endl; } break; case 2: it=author.find(query); if(it==author.end()) cout<<"Not Found"<<endl; else { for(pos=it->second.begin();pos!=it->second.end();pos++) cout<<*pos<<endl; } break; case 3: it=keyword.find(query); if(it==keyword.end()) cout<<"Not Found"<<endl; else { for(pos=it->second.begin();pos!=it->second.end();pos++) cout<<*pos<<endl; } break; case 4: it=publisher.find(query); if(it==publisher.end()) cout<<"Not Found"<<endl; else { for(pos=it->second.begin();pos!=it->second.end();pos++) cout<<*pos<<endl; } break; case 5: it=year.find(query); if(it==year.end()) cout<<"Not Found"<<endl; else { for(pos=it->second.begin();pos!=it->second.end();pos++) cout<<*pos<<endl; } break; } } return 0;}方法三：最后试了一下线性搜索，居然过了，看来时间没卡的很严。。。
#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct book{ char id[10]; char title[85]; char author[85]; char keywords[100]; char publisher[85]; char year[10];}BOOK;BOOK book_list[10005];int compare(const void *a,const void *b){ BOOK a1 = *(BOOK *)a; BOOK b1 = *(BOOK *)b; return strcmp(a1.id,b1.id);}void QueryBook(int qnum, char qword[],int nBook){ bool found = false; for(int i=0;i<nBook;i++) { BOOK curbook = book_list[i]; switch(qnum) { case 1: // title if(strcmp(qword,curbook.title)==0) { printf("%s\n",curbook.id); found = true; } break; case 2: // author if(strcmp(qword,curbook.author)==0) { printf("%s\n",curbook.id); found = true; } break; case 3: // keyword if(strstr(curbook.keywords,qword)!=NULL) { printf("%s\n",curbook.id); found = true; break; } break; case 4: // publisher if(strcmp(qword,curbook.publisher)==0) { printf("%s\n",curbook.id); found = true; } break; case 5: // year if(strcmp(qword,curbook.year)==0) { printf("%s\n",curbook.id); found = true; } break; } } if(!found) printf("Not Found\n");}int main(){ int N,M; scanf("%d",&N); for(int i=0;i<N;i++) { scanf("%s",book_list[i].id); getchar(); gets(book_list[i].title); gets(book_list[i].author); gets(book_list[i].keywords); gets(book_list[i].publisher); scanf("%s",book_list[i].year); } qsort(book_list,N,sizeof(BOOK),compare); scanf("%d",&M); for(int i=0;i<M;i++) { int qnum; char qword[100]; scanf("%d: ",&qnum); gets(qword); printf("%d: %s\n",qnum,qword); QueryBook(qnum,qword,N); } return 0;}