终于有时间写点东西了，正巧最近在准备 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 五项查找书目。

# 思路

1. 图书个数 N 数量级可以达到 10^5，一定要考虑如何减少时间复杂度。Lz 的想法是输入的便利不可避免，尽量在输入的同时把其他的操作一并解决。所以使用了五个 map，map 的 value 值选择了 set，以便减少排序的时间。
2. 一开始 Lz 的想法是插入 map 值的时候要先判断 map 里面有没有这个 key，没有的话可以直接令，有的话只能取出来 push_back().后来看了一个博客才发现，可以直接 insert().顿时觉得茅塞顿开。
3. 第三个使用 cin 输入数据的时候，要注意'\n'这些有么有单独占了一个 getline。最好的方法就是老老实实用 sannf,把多余不要的字符都写出来。
4. 第四个测试点一直过不去，后来才发现原来没注意到 id 是 7 位数的。哎，还是题目不敏感。
5. 使用函数时，当数据量大的时候，尽量用&引用，否则时间复杂度太大，过不去。
6. 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;
}