【PAT甲级】1022 Digital Library

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1022 Digital Library (pintia.cn)
🔑中文翻译：数字图书馆
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

1022 Digital Library

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⁴) 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题意

接下来包含这 N 本书的具体信息，每本书的相关信息占 6 行：

• 第一行：书的 ID，一个 7 位数字。
• 第二行：书名，一个长度不超过 80 的字符串。
• 第三行：作者，一个长度不超过 80 的字符串。
• 第四行：关键词，每个关键词的长度均不超过 10，且关键词中不包含空格，关键词之间用空格隔开。
• 第五行：出版商，一个长度不超过 80 的字符串。
• 第六行：出版年限，一个在 [1000,3000] 范围内的 4 位数字。

一本书，只有一位作者，包含的关键词不超过 5 个。

总共不超过 1000 个不同的关键词，不超过 1000 个不同的出版商。

图书信息介绍完毕后，有一行包含一个整数 M，表示查询次数。

接下来 M 行，每行包含一个查询，具体格式如下：

• 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，查询出版年限。注意，这个年限可能包含前导 0 。

对于每个查询，首先将查询信息输出在一行中。

接下来若干行，每行输出一个查询到的相关书籍的 ID，按升序顺序排列。

如果查询不到相关书籍，则输出 Not Found。

思路

1. 面对这么多复杂信息的题，我们可以用结构来存储所有信息。输入信息的时候有些是一行数据，所以要用到 getline，同时如果想将该行数据根据空格分开存储的话例如 keyword ，就需要用到 stringstream 。
2. 因为这道题给的数据范围为 $N\le 10^4,M\le 1000$ ，最坏情况下是 $N\ast M=10^7<10^8$ ，故可以直接暴力求解。我们将给定的信息与数组中书的所有信息作对比，然后将满足要求的用另外一个数组存起来，最后再排序输出即可。注意，这里是按照 ID 的字典序升序排序。

代码

#include
using namespace std;

//存储书的信息
struct book
{
    string id, name, author;
    set<string> keywords;
    string publisher, year;
};

int main()
{
    int n, m;
    cin >> n;

    //输入书的信息
    vector<book> books;
    for (int i = 0; i < n; i++)
    {
        string id, name, author, publisher, year;
        set<string> keywords;
        cin >> id;    //输入书的id
        getchar();
        getline(cin, name);      //输入书名
        getline(cin, author);    //输入作者
        string line;
        getline(cin, line);  //输入关键字
        stringstream ssin(line);
        string str;
        while (ssin >> str)    keywords.insert(str);
        getline(cin, publisher); //输入出版商
        cin >> year;  //输入出版年限
        books.push_back({ id,name,author,keywords,publisher,year });
    }

    cin >> m;
    getchar();
    //查询书的信息
    while (m--)
    {
        string info;
        getline(cin, info);
        cout << info << endl;
        int t = info[0];
        info = info.substr(3);

        vector<string> res; //存储答案
        if (t == '1')    //根据书名查询
        {
            for (auto& b : books)
                if (b.name == info)
                    res.push_back(b.id);
        }
        else if (t == '2')   //根据作者查询
        {
            for (auto& b : books)
                if (b.author == info)
                    res.push_back(b.id);
        }
        else if (t == '3')   //根据关键字查询
        {
            for (auto& b : books)
                if (b.keywords.count(info))
                    res.push_back(b.id);
        }
        else if (t == '4')   //根据出版商查询
        {
            for (auto& b : books)
                if (b.publisher == info)
                    res.push_back(b.id);
        }
        else    //根据出版年限查询
        {
            for (auto& b : books)
                if (b.year == info)
                    res.push_back(b.id);
        }

		//判断是否查找到了书
        if (res.empty()) puts("Not Found");
        else
        {
            sort(res.begin(), res.end());	//根据id排序
            for (auto& x : res)    cout << x << endl;
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90