【UVA-230】Borrowers【紫书】

【UVA-230】Borrowers【紫书】

问题链接:https://vjudge.net/problem/UVA-230

Solution:

参考了绿书上描述的方法。我们使用vector来存全部书籍的数据,之后使用map来将书名映射到vector中的位置,开两个set分别管理剩下的书和刚还回来的书,利用struct实现一个伪函数,传给set模板第二参数,用它来进行题意上的排序【如果不清楚伪函数,可以去翻看《C++ Primer Plus》,或者直接百度一下】。

关于格式字符串,我们将一行字符串读进来后

使用for(; str[i] != ‘ ‘; i++);来跳过非空格字符,

使用for(; str[i] == ‘ ‘; i++);来跳过空格字符。

接着使用string类的assign()函数赋值将子串赋值给另一个字符串。

#include <iostream>
#include <set>
#include <unordered_map>
#include <string>
#include <vector>
// #define DBG

using namespace std;

struct Book {
    string title, author;
};
vector<Book> data;
struct cmp {
    bool operator() (const int a, const int b) {
        return data[a].author < data[b].author || (data[a].author == data[b].author && data[a].title < data[b].title);
    }
};
set<int, cmp> rest, back;
unordered_map<string, int> titlemap;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string str;
    int gblcnt;
    Book tmp;
    while (getline(cin, str) && str[0] != 'E') {
        gblcnt = data.size();
        int i;
        for (i = 1; str[i] != '\"'; i++);
        tmp.title.assign(str, 0, i + 1);
        for (i++; str[i] == ' '; i++);
        for (; str[i] != ' '; i++);
        for (; str[i] == ' '; i++);
        tmp.author.assign(str, i, str.size() - i);
#ifdef DBG
        cout << "title: " << tmp.title << endl;
        cout << "author: " << tmp.author << endl;
#endif
        data.push_back(tmp);
        titlemap[tmp.title] = gblcnt;
        rest.insert(gblcnt);
    }
    while (cin >> str && str[0] != 'E') {
#ifdef DBG
        cout << "operation: " << str << endl;
#endif
        if (str[0] == 'B') {
            string tmp;
            getline(cin, tmp);
            int i;
            for (i = 0; tmp[i] == ' '; i++);
            str.assign(tmp, i, tmp.size() - i);
            rest.erase(titlemap[str]);
        } else if (str[0] == 'R') {
            string tmp;
            getline(cin, tmp);
            int i;
            for (i = 0; tmp[i] == ' '; i++);
            str.assign(tmp, i, tmp.size() - i);
            back.insert(titlemap[str]);
        } else {
            set<int, cmp>::iterator ite;
            for (auto idx : back) {
                rest.insert(idx);
                ite = rest.find(idx);
                if (ite == rest.begin())
                    cout << "Put " << data[idx].title << " first\n";
                else
                    cout << "Put " << data[idx].title << " after " << data[*(--ite)].title << "\n";
            }
            back.clear();
            cout << "END\n";
        }
    }
    return 0;
}