UVA 230 Borrowers（多种STL运用）

水深无声 2022-06-07 02:58 108阅读 0赞

**详细题目：**https://vjudge.net/problem/UVA-230

**思路：**

根据题意先对各本书进行排序（按ASCII码先作者后书名），建立一个结构体 book 对每本书的作者和状态（入藏，借出，归还但未上架）进行储存，并通过建立 map< bookname-book > 的键值关系。对于每次 SHELVE 操作，找到第三种状态的书，确定其插入的位置（先前排序的作用于此）。

**代码：**

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <string>
    #include <vector>
    #include <map>
    
    using namespace std;
    
    struct book
    {
        string author;
        int status;
    };
    
    map<string,book> books;
    vector<string> name;
    
    bool cmp(string nameA,string nameB)
    {
        if(books[nameA].author==books[nameB].author)    return nameA<nameB;
        else return books[nameA].author<books[nameB].author;
    }
    
    int main()
    {
        string s,t;
        book p;
        while(getline(cin,s))
        {
            if(s == "END") break;
            t = s.substr(0, s.find_last_of("\"")+1);
            p.author = s.substr(s.find_last_of("\"")+1);
            name.push_back(t);
            books[t]= p;
        }
        sort(name.begin(), name.end(), cmp);//依题排序
    
        for(int i = 0; i < name.size(); i++)//所有书状态为在藏
            books[name[i]].status = 0;
        while(cin >> s)
        {
            if(s == "END") break;
            if(s == "BORROW")
            {
                getchar();
                getline(cin, t);//取书名,状态为借出
                books[t].status = -1;
            }
            if(s == "RETURN")
            {
                getchar();
                getline(cin, t);
                books[t].status = 1;//状态为归还但未上架
            }
            if(s == "SHELVE")
            {
                for(int i = 0; i < name.size(); i++)
                {
                    if(books[name[i]].status == 1)
                    {
                        //找到状态为归还但未上架的书
                        int j;
                        for(j = i; j >-1; --j)//寻找状态为在藏的书而且它排在要插入的书的前面
                            if(books[name[j]].status == 0) break;
                        if(j > -1)//找到
                            cout << "Put " << name[i] << " after " << name[j] << endl;
                        else//找不到，意味着要插入的书是顺序为第一本书
                            cout << "Put " << name[i] << " first" << endl;
                        books[name[i]].status = 0;//已上架，状态变为在藏
                    }
                }
                cout << "END" << endl;
            }
        }
        return 0;
    }