PAT甲级——A1022 Digital Library-白红宇

PAT甲级——A1022 Digital Library

阅读量：4540 次

发布时间：2019-06-08

本文共 5270 字，大约阅读时间需要 17 分钟。

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

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

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: blablabla

Sample Output:

1: The Testing Book111111122222222: Yue Chen111111133333333: keywords1111111222222233333334: ZUCS Print11111115: 2011111111122222223: blablablaNot Found

第一种方法

以时间换空间，就是个ID保留一组信息，查询时遍历查询

但可能导致时间复杂度过大

第二种方法[推荐使用方法二]

以空间换时间，每种信息对应一个ID，查找时，时间复杂度为O(1)

但可能导致空间复杂度太大

注意一些字符输入的细节

1 #include 
     
        2 #include 
        3 #include 
       
          4 #include 
        
           5 #include 
         
            6 using namespace std;  7   8 方法一：  9 struct node 10 { 11     string name, author, keywords, publisher, year; 12 }; 13 int main() 14 { 15     int N, M; 16     string ID; 17     cin >> N; 18     map
          
           data; 19 for (int i = 0; i < N; ++i) 20 { 21 node book; 22 cin >> ID; 23 getchar();//去除回车键 24 getline(cin, book.name); 25 getline(cin, book.author); 26 getline(cin, book.keywords); 27 getline(cin, book.publisher); 28 cin >> book.year; 29 data[ID] = book; 30 } 31 cin >> M; 32 getchar();//去除回车键 33 for (int i = 0; i < M; ++i) 34 { 35 string str; 36 bool is = true; 37 getline(cin, str); 38 cout << str << endl; 39 int index = str[0] - '0'; 40 str.assign(str.begin() + 3, str.end()); 41 for (auto ptr = data.begin(); ptr != data.end(); ++ptr) 42 { 43 switch (index) 44 { 45 case 1: 46 if (ptr->second.name == str) 47 { 48 is = false; 49 cout << ptr->first << endl; 50 } 51 break; 52 case 2: 53 if (ptr->second.author== str) 54 { 55 is = false; 56 cout << ptr->first << endl; 57 } 58 break; 59 case 3: 60 if (ptr->second.keywords.find(str) !=-1) 61 { 62 is = false; 63 cout << ptr->first << endl; 64 } 65 break; 66 case 4: 67 if (ptr->second.publisher == str) 68 { 69 is = false; 70 cout << ptr->first << endl; 71 } 72 break; 73 case 5: 74 if (ptr->second.year == str) 75 { 76 is = false; 77 cout << ptr->first << endl; 78 } 79 break; 80 default: 81 break; 82 } 83 } 84 if (is) 85 cout << "Not Found" << endl; 86 } 87 return 0; 88 } 89 90 //方法二 91 void findInfo(unordered_map

>&data,string &str)//传参一定要用引用，否则最后一组数据可能会超时 92 { 93 if(data.find(str)==data.end()) 94 printf("Not Found\n"); 95 else 96 { 97 for (auto ptr = data.find(str)->second.begin(); ptr != data.find(str)->second.end(); ++ptr) 98 printf("%07d\n", *ptr); 99 }100 }101 int main()102 {103 int N, M, ID;104 scanf("%d", &N);105 string til, aut, keys, pub, yea;106 unordered_map

>title, author, keywords, publisher, year;//因为key不唯一107 for (int i = 0; i < N; ++i)108 {109 scanf("%d\n", &ID);//不用清除回车键110 getline(cin, til);111 title[til].insert(ID);112 getline(cin, aut);113 author[aut].insert(ID);114 while (cin >> keys)115 {116 keywords[keys].insert(ID);117 char c = getchar();118 if (c == '\n')break;119 }120 getline(cin, pub);121 publisher[pub].insert(ID);122 getline(cin, yea);123 year[yea].insert(ID);124 }125 scanf("%d\n", &M);126 for (int i = 0; i < M; ++i)127 {128 string str;129 getline(cin, str);130 cout << str << endl;131 int index = str[0] - '0';132 str.assign(str.begin() + 3, str.end());133 if (index == 1) findInfo(title, str);134 else if (index == 2) findInfo(author, str);135 else if (index == 3) findInfo(keywords, str);136 else if (index == 4) findInfo(publisher, str);137 else if (index == 5) findInfo(year, str);138 else printf("Not Found\n");139 }140 return 0;141 }

转载于:https://www.cnblogs.com/zzw1024/p/11247296.html