第四章排序 AcWing 1499. 数字图书馆

朴灿烈づ我的快乐病毒、 2023-09-24 13:55 96阅读 0赞

## 第四章 排序 AcWing 1499. 数字图书馆 ##

### 原题链接 ###

[AcWing 1499. 数字图书馆][AcWing 1499.]

### 算法标签 ###

排序 字符串处理

### 思路 ###

依题意模拟  
注意存储类型选择  
![在这里插入图片描述][a626ff353bb74f6389f82967a7a71912.png]  
若采用string数组存储关键词, 时间复杂度高于使用set存储 。

### 代码 ###

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define pii pair<int, int>
    #define rep(i, a, b) for(int i=a; i<b; ++i)
    #define Rep(i, a, b) for(int i=a; i>=b; --i)
    #define debug(a) cout<<#a<<"="<<a<<endl;
    #define debugi(i) printf("i = %lld\n", i)
    const int N=10005;
    int n, m;
    ump<string, vector<int>> gra;
    vector<int> q[4];
    inline int rd(){
        int s=0, w=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-'){
                w=-1;    
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            s=s*10+ch-'0';
            ch=getchar();
        }
        return s*w;
    }
    struct Book{
        string id, name, auth;
        set<string> keys;
        string pub, year;
    };
    bool cmp(Book A, Book B){
        return A.id<B.id;
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n,m;
        cin>>n;
        vector<Book> books;
        while(n--){
            string id, name, auth;
            cin>>id;
            // 使用getline()函数读取下一行内容前， 需要使用getchar()处理当前行末换行符
            getchar();
            getline(cin, name);
            getline(cin, auth);
            string l;
            getline(cin, l);
            stringstream ssin(l);
            string key;
            set<string> keys;
            while(ssin>>key){
                keys.insert(key);
            }
            string pub, year;
            getline(cin, pub);
            cin>>year;
            books.push_back({id, name, auth, keys, pub, year});
        }
        cin>>m;
        getchar();
        string s;
        while(m--){
            getline(cin, s);
            cout<<s<<"\n";
            vector<string> ids;
            if(s[0]=='1'){
                rep(i, 0, books.size()){
                    if(books[i].name==s.substr(3)){
                        ids.push_back(books[i].id);
                    }
                }
            }else if(s[0]=='2'){
                rep(i, 0, books.size()){
                    if(books[i].auth==s.substr(3)){
                        ids.push_back(books[i].id);
                    }
                }
            }else if(s[0]=='3'){
                rep(i, 0, books.size()){
                    if(books[i].keys.count(s.substr(3))){
                        ids.push_back(books[i].id);
                    }
                }
            }else if(s[0]=='4'){
                rep(i, 0, books.size()){
                    if(books[i].pub==s.substr(3)){
                        ids.push_back(books[i].id);
                    }
                }
            }else if(s[0]=='5'){
                rep(i, 0, books.size()){
                    if(books[i].year==s.substr(3)){
                        ids.push_back(books[i].id);
                    }
                }
            }
            if(ids.empty()){
                cout<<"Not Found"<<"\n";
            }else{
                sort(ids.begin(),  ids.end());
                rep(i, 0, ids.size()){
                    cout<<ids[i]<<"\n";
                }
            }
        }
        return 0;
    }

### 总结 ###

1 使用`getline()`函数读取下一行内容前， 需要使用`getchar()`处理当前行末换行符， 否则`getline()`将读取当前行末换行符  
2 使用`stringstream ssin`进行格式化读取，若遇到空格该次读取会自动结束， 进行下次读取  
获取语句中的单词

vector<string> get(string s){
    	stringstream ssin(s);
    	vector<string> ans;
    	string x;
    	while(ssin>>x){
            ans.push_back(x);
        }        
        return ans;
    }

### 参考文献 ###

[AcWing 1499. 数字图书馆（PAT甲级辅导课）y总视频讲解][AcWing 1499. _PAT_y]  
[AcWing 1499. 数字图书馆y总代码][AcWing 1499. _y]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 1499.]: https://www.acwing.com/problem/content/1501/
[a626ff353bb74f6389f82967a7a71912.png]: https://img-blog.csdnimg.cn/a626ff353bb74f6389f82967a7a71912.png
[AcWing 1499. _PAT_y]: https://www.acwing.com/video/1018/
[AcWing 1499. _y]: https://www.acwing.com/activity/content/code/content/272621/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png