UVA230 Borrowers 图书管理系统 解题报告

题目链接

https://vjudge.net/problem/UVA-230

题目大意

你的任务是模拟一个图书管理系统。首先输入若干图书的标题和作者（标题各不相同，以END结束），然后是若干指令：BORROW指令表示借书，RETURN指令表示还书，SHELVE指令表示把所有已归还但还未上架的图书排序后依次插入书架并输出图书标题和插入位置（可能是第一本书或者某本书的后面）。

图书排序的方法是先按作者从小到大排，再按标题从小到大排。在处理第一条指令之前，你应当先将所有图书按照这种方式排序。

解题思路

用map< string, int >维护书名与书的状态之间的映射，1为在书架，2为借出，3为归还但不在书架，剩下的就全都是按照题意硬模拟，用最纯粹的，最朴素的，最丁真（bushi）的循环遍历是足够AC的，也就懒得想优化了，细节很多，具体参考代码和注释。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1000000007;
struct Book {
    string title;
    string author;
    bool operator < (const Book &other) const {
        if (author == other.author)
            return title < other.title;
        return author < other.author;
    }
};
vector<Book> books;
map<string, int> state; // 书的状态，1为在书架，2为借出，3为归还但不在书架

void solve() {
    string s, title, author;
    while (getline(cin, s), s != "END") {
        int pos = s.find("\"", 1);
        title = s.substr(1, pos);
        pos += 5;
        author = s.substr(pos);
        books.push_back({title, author});
        state[title] = 1;
    }
    sort(books.begin(), books.end());
    while (getline(cin, s), s != "END") {
        if (s[0] == 'B') {
            title = s.substr(8);
            state[title] = 2;
        } else if (s[0] == 'R') {
            title = s.substr(8);
            state[title] = 3;
        } else {
            for(int i = 0 ; i < books.size() ; i++) {
                if (state[books[i].title] == 3) {
                    int j;
                    for (j = i - 1; j >= 0; j--) {
                        if (state[books[j].title] == 1) {
                            break;
                        }
                    }
                    cout << "Put \"" << books[i].title << " ";
                    if (j != -1) {
                        cout << "after \"" << books[j].title <<endl;
                    } else {
                        cout << "first" << endl;
                    }
                    state[books[i].title] = 1;
                }
            }
            cout << "END\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    solve();
    return 0;
}