PAT_甲级_1022 Digital Library (30分) (C++)【map+set+STL】

目录

​​1，题目描述​​

​​题目大意​​

​​输入​​

​​输出​​

​​2，思路​​

​​数据结构​​

​​注意​​

​​3，代码​​

1，题目描述

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书本总数（0-10^4）;

接下来N块：每块6行，为书本的信息。依次是：

• ID（7位数字），
• title标题（不超过80个字符），
• author作者（不超过80个字符），
• key words关键词（每个关键词不超过10个字符，各关键词之间用空格隔开），
• publisher出版商（不超过80个字符），
• published year版日期（4位数字，[1000,3000]）

接下来一行：M条查询数（<=1000）

最后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

输出

对每个查询，首先输出原始的查询，然后按照增序输出查找结果（书本ID），每个结果占一行；

若无查询结果，输出Not Found；

2，思路

这一题，题意比较明确，就是直接的查找。本想设计结构体，直接将每一本书的所有信息添加进去，查找时一项项搜。但和网上的大神对比过后，感觉，，，太low了（数据量比较大，一项项查找效率太低，很可能会超时）

大神的思路是：为每一种查询（共有5种，对应数字1-5）创建一个map，键是可能的查询，值是书籍的ID（这里是int型），这样对每一种查询，都可以根据键是否存在，以及键对应的值来输出答案；（在数据的输入过程中，就完成了对书籍的分类，妙啊！）

数据结构

• map< string, set<int> > Title, Author, Key, Pub, Year：存储可能的查询以及对应的书籍id（set避免重复），这样给出查询就能迅速找到对应的id；

注意

• 若将书籍ID作为数字存储的话，输出时要用printf("%07d", ID)；
• 书籍的查找中，第一个数字是查找的类型，而不是查询的编号；
• 当使用getline函数时，若使用此函数之前还有一行输入的数据，记得把上一行输入数据的\n也读取掉（否则会出现无法预测的情况）；

3，代码

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

map< string, set<int> > Title, Author, Key, Pub, Year;
void query(map< string, set<int> > &way, string &s){                // !!!传引用 不然会超时
    if(way.find(s) != way.end()){                                   //判断map中键s是否有对应的值
        for(auto it = way[s].begin(); it != way[s].end(); it++){
            printf("%07d\n", *it);
        }
    }else{
        printf("Not Found\n");
    }

}

int main(){
//#ifdef ONLINE_JUDGE
//#else
//    freopen("1.txt", "r", stdin);
//#endif

    int n = 0, id, m;                                               //n书籍数目 id书籍编号 m查询条数
    string title, author, key, pub, year;
    scanf("%d\n", &n);
    for(int i = 0; i < n; i++){
        scanf("%d\n", &id);                                         // !!!下一行使用getline函数 这里读取时注意加\n

        getline(cin, title);                                        //一次读取一行
        Title[title].insert(id);

        getline(cin, author);
        Author[author].insert(id);

        while(cin>>key){                                            //读取多个以空格隔开的关键字 直到换行符为止
            Key[key].insert(id);
            char c = getchar();
            if(c == '\n') break;                                    //否则即为空格 继续循环
        }

        getline(cin, pub);
        Pub[pub].insert(id);

        getline(cin, year);
        Year[year].insert(id);
    }

    scanf("%d\n", &m);
    for(int i = 0; i < m; i++){
        int num;
        string temp;
        scanf("%d: ", &num);                                        //截取数字部分
        getline(cin, temp);
        cout<<num<<": "<<temp<<endl;
        if(num == 1) query(Title, temp);
        else if(num == 2) query(Author, temp);
        else if(num == 3) query(Key, temp);
        else if(num == 4) query(Pub, temp);
        else if(num == 5) query(Year, temp);
    }

    return 0;
}