PAT 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 (≤10​4 ) 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: 3 1111111 The Testing Book Yue Chen test code debug sort keywords ZUCS Print 2011 3333333 Another Testing Book Yue Chen test code sort keywords ZUCS Print2 2012 2222222 The Testing Book CYLL keywords debug book ZUCS Print2 2011 6 1: The Testing Book 2: Yue Chen 3: keywords 4: ZUCS Print 5: 2011 3: blablabla

Sample Output: 1: The Testing Book 1111111 2222222 2: Yue Chen 1111111 3333333 3: keywords 1111111 2222222 3333333 4: ZUCS Print 1111111 5: 2011 1111111 2222222 3: blablabla Not Found

题目解读

给你n本书的信息，每本书都包括id，title，author，keywords，publisher，publishyear六部分信息，然后有m次查询，每次查询要求输出所有满足这个查询条件的书的id，如果有多个，按照id大小顺序输出，如果一个都没有，输出"Not found"，查询可以是根据title，author，keyword，publisher，publishyear这五种条件任何一种查询。

题解及注意事项

这个题其实不难，只是有好几处细节需要注意，我们先来看思路：

• 首先，每一类查询条件都有可能得到多个id，所以肯定要有一个map<k, v>吧，==k就是输入的查询条件字段==，比如输入的title，author什么的，至于v肯定是保存多本书。
• 其次，我需不需要创建一个数据结构来保存每本书的信息。当然不用，我们每种查询条件下只需要输出书的id就可以了，所以==map集合的V只需要保存多个id==。那采用什么数据结构呢？当然是set，因为set既能存储多个，又能自动去重，还能自动排序，多么完美的适合这个题目。所以我们用的是map<string, set<int>>。
• 因为有五类查询条件，所以我创建五个引射表 map<string, set<int>> titlemap, authormap, keywordmap, publishermap, publishyearmap;然后在录入每本书的信息时，将书的id插入到对应的每个map中，

		// 以录入一本书信息为例
        // cin >> id; 
        scanf("%d\n", &id);
        // 这些信息可能中间包含空格，所以需要读整行
        getline(cin, title);
        // 在对应的映射集中加入这本书id
        titlemap[title].insert(id);
        getline(cin, author);
        // 在对应的映射集中加入这本书id
        authormap[author].insert(id);
        // 关键字与之不同，一本书有多个关键字，空格分隔
        while (cin >> keyword) {
            keywordmap[keyword].insert(id);
            char ch = getchar();
            // 读完本行最后一个关键字
            if (ch == '\n') break;
        }
        // 读出版社
        getline(cin, publisher);
        // 在对应的映射集中加入这本书id
        publishermap[publisher].insert(id);
        // 读出版年
        getline(cin, publishyear);
        // 在对应的映射集中加入这本书id
        publishyearmap[publishyear].insert(id);

• 查询的时候，我们只需要根据输入的查询类别和参数，去对应的映射集找相应的键值就可以了。

踩坑1，读一整行

看到我上面代码中的读取id字段了吧，为什么要注释cin>>id，而用scanf("%d,\n", &id)，因为id下面是title，而title中可能包含空格，如 hello c++ 这种，scanf和cin在遇到空格时都会结束，所以我们要用getLine()来读取title，author，publisher等信息，但是我读完id才能读title，我如果用cin读id，它遇到行末\n就结束了，不会自己换行，接着用getline()去读title，就只能读进去一个这一行剩下的\n。肯定出错。所以这里要用scanf把那个\n读走，换到下一行。

踩坑2，读 多个关键词

上面说了，==读title，author，publisher，publishyear要读取整行==（publishyear其实是个整数，我们是为了操作统一把它读成字符串，不然五种查询条件，四种参数是字符串，一种是整数，我岂不是要写两个函数），但是一个文章的多个关键字在同一行，用空格分隔，这要怎么读？读取一行，再字符串分隔吗？c++好像没有现成的split()函数，所以我们可以这样读取

		// 关键字与之不同，一本书有多个关键字，空格分隔
        while (cin >> keyword) {
            keywordmap[keyword].insert(id);
            // 在对应的映射集中加入这本书id
            char ch = getchar();
            // 读完本行最后一个关键字
            if (ch == '\n') break;
        }

cin遇到空格或\n结束，刚好一次读到一个单词，然后最后一个单词的末尾是换行符。

踩坑3，查询时输入数据的空格

请看题目给出的查询时的输入，6表示有6次查询，每个查询，数字代表是按照那个字段查询，然后它后面有一个空格。千万记得把这个空格读走，剩下的才是参数，而且参数是一个长的字符串，中间可能包含空格，还是要用getLine()。

6
1: The Testing Book
2: Yue Chen
3: keywords
4: ZUCS Print
5: 2011
3: blablabla

踩坑4，函数传参不加&造成超时

其实这个不算坑了，就是一个细节问题，我们知道如果是值传递的时候会有一个值拷贝的过程，当这个参数特别大（占用空间多）的时候，这个拷贝过程会浪费空间和时间，而c++的引用就很好的避免了这个问题，所以记得加&

// kvmap是键值对映射集，key是键，也就是输入的参数
void query(map<string, set<int>> &kvmap, string &key) {

完整代码

注意事项都说完了，就贴一下我的代码吧，注释日常详细！！！

#include <iostream>
#include <map>
#include <set>
using namespace std;

// 为每个指标建立一对多映射集合
// 因为既要既可能包含多个，又要求找到多个多个时按bookid递增输出，那么用set就好了，既能去重，又能自动排序
map<string, set<int>> titlemap, authormap, keywordmap, publishermap, publishyearmap;

// kvmap是键值对映射集，key是键，也就是输入的参数
void query(map<string, set<int>> &kvmap, string &key) {
    // 这个键是否有值
    auto res = kvmap.find(key);
    // 有值，
    if (res != kvmap.end()) {
        // 注意输出为7位id
        for (auto id : kvmap[key])
            printf("%07d\n", id);
    // 无值
    } else {
        cout << "Not Found" << endl;
    }
}

int main() {

    // n本书
    int n;
    cin >> n;
    int id; // 当前书id
    // 当前书 标题、作者、关键词、出版社、出版年
    string title, author, keyword, publisher, publishyear;
    while (n-- > 0) {
        // cin >> id;
        scanf("%d\n", &id);
        // 这些信息可能中间包含空格，所以需要读整行
        getline(cin, title);
        // 在对应的映射集中加入这本书
        titlemap[title].insert(id);
        getline(cin, author);
        authormap[author].insert(id);
        // 关键字与之不同，一本书有多个关键字，空格分隔
        while (cin >> keyword) {
            keywordmap[keyword].insert(id);
            char ch = getchar();
            // 读完本行最后一个关键字
            if (ch == '\n') break;
        }
        // 读出版社
        getline(cin, publisher);
        publishermap[publisher].insert(id);
        getline(cin, publishyear);
        publishyearmap[publishyear].insert(id);
    }
    int m;
    // m次查询
    cin >> m;
    // 查询格式 num: xxxxx xxxx
    int num; // 查询类别
    // 查询参数
    string temp;
    while (m-- > 0) {
        scanf("%d: ", &num);
        getline(cin, temp);
        cout << num << ": " << temp << endl;
        // 根据标题查
        if (num == 1) query(titlemap, temp);
        // 根据作者查
        else if (num == 2) query(authormap, temp);
        // 根据关键字查
        else if (num == 3) query(keywordmap, temp);
        // 根据出版社查
        else if (num == 4) query(publishermap, temp);
        // 根据出版年份查
        else if (num == 5) query(publishyearmap, temp);
    }

    return 0;

}