1022 Digital Library 30 ☆☆☆
终于有时间写点东西了,正巧最近在准备PAT考试,想把PAT思路这部分做一下。
github地址:https://github.com/iofu728/PAT-A-by-iofu728
难度:☆☆☆
关键词:map,引用传参,get输入
题目
1022.Digital Library (30)
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”
大意
建立一个图书馆图书数据库,通过title,author,publish,key,year五项查找书目。
思路
- 图书个数N数量级可以达到10^5,一定要考虑如何减少时间复杂度。Lz的想法是输入的便利不可避免,尽量在输入的同时把其他的操作一并解决。所以使用了五个map,map的value值选择了set,以便减少排序的时间。
- 一开始Lz的想法是插入map值的时候要先判断map里面有没有这个key,没有的话可以直接令,有的话只能取出来push_back().后来看了一个博客才发现,可以直接insert().顿时觉得茅塞顿开。
- 第三个使用cin输入数据的时候,要注意'\n'这些有么有单独占了一个getline。最好的方法就是老老实实用sannf,把多余不要的字符都写出来。
- 第四个测试点一直过不去,后来才发现原来没注意到id是7位数的。哎,还是题目不敏感。
- 使用函数时,当数据量大的时候,尽量用&引用,否则时间复杂度太大,过不去。
- map的循环使用C++11的for(auto it:),it在这里是一个迭代器,对map有it.first,it.second表示其key-value.
code
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
using namespace std;
int n, m;
map<string, set<int> > titles, authors, publishs, years, keys;
void input(map<string, set<int> > &mmp, string &str) {
if (mmp.find(str) == mmp.end()) {
cout << "Not Found\n";
} else {
for (auto it = mmp[str].begin(); it != mmp[str].end(); ++it) {
printf("%07d\n", *it);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
string title, author, key, publish, year;
int id;
scanf("%d\n", &id);
getline(cin, title);
getline(cin, author);
while (cin >> key) {
keys[key].insert(id);
char c = getchar();
if (c == '\n') break;
}
getline(cin, publish);
getline(cin, year);
titles[title].insert(id);
authors[author].insert(id);
publishs[publish].insert(id);
years[year].insert(id);
}
int num;
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
scanf("%d: ", &num);
string str;
getline(cin, str);
cout << num << ": " << str << endl;
switch (num) {
case 1:
input(titles, str);
break;
case 2:
input(authors, str);
break;
case 3:
input(keys, str);
break;
case 4:
input(publishs, str);
break;
case 5:
input(years, str);
break;
}
}
return 0;
}