问题描述
p230相关说明：本题为《算法竞赛入门经典（第2版）》习题 5-8
解法一：模拟 + 排序
直接模拟即可，按照题目所属规则排序，排序后的索引可用来建立 title 到对应 id 的映射关系，用来维护信息时快速索引 books[id[title]]. 但需注意到容易 WA 的情况：书架中有多个 title 和 author 相同书籍的情况（此时找到如何/是否能找到前一本书的位置需要好好考虑）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <bits/stdc++.h> using namespace std; struct Book { string title; string author; string status; bool operator<(const Book &b) const { return author < b.author || (author == b.author && title < b.title); } }; Book parse_book(string &line) { // split line into title and author Book book; int by_pos = line.find(" by "); book.title = line.substr(0, by_pos); book.author = line.substr(by_pos + 4); book.status = "SHELVE"; return book; } void do_shelve(vector<Book> &books) { for (int i = 0; i < books.size(); ++i) if (books[i].status == "RETURN") { cout << "Put " << books[i].title; int j = i - 1; // find the previous book (if shelved) for (; j >= 0 && books[j].status != "SHELVE"; --j); cout << (j < 0 ? " first" : " after " + books[j].title) << endl; books[i].status = "SHELVE"; } cout << "END" << endl; } int main() { vector<Book> books; string line; while (getline(cin, line) && line != "END") books.push_back(parse_book(line)); sort(books.begin(), books.end()); map<string, int> id; // title -> id for (int i = 0; i < books.size(); i++) id[books[i].title] = i; while (getline(cin, line) && line != "END") { string command = line.substr(0, line.find(" ")); string title = line.substr(line.find(" ") + 1); if (command == "SHELVE") do_shelve(books); else books[id[title]].status = command; } return 0; } |
|
1 |
#TODO |
