[开发测试]算法竞赛入门经典 习题5-8

UVa230

Borrowers

图书馆书架上有一些已经排序（首先按照作者升序排序、然后按照书名升序排序）的书，使用程序来模拟借书和还书的过程。

在输入SHELVE指令时，需要将已经RETURN的书按照已经排序的顺序输出其在书架上的位置，这就要求对已经RETURN的书也进行排序，同时书架上的被BORROW的书会影响需要上架的书的位置，因此创建shelf、borrowed和returned三个书架会比较方便。

uDebug上有两个超长的测试用例过不去，但是提交到UVa上也AC了。

#include <iostream>
#include <set>
#include <string>

using namespace std;

struct Book
{
	string title;
	string author;
	Book(const string &title, const string &author)
		: title(title), author(author) {};
	bool operator<(const Book &book) const
	{
		if (author < book.author) return true;
		else if (author == book.author) return title < book.title;
		else return false;
	}
};

set<Book>::iterator SearchBookByTitle(set<Book> &shelf, const string &title)
{
	for (auto iter = shelf.begin(); iter != shelf.end(); iter++)
	{
		if (iter->title == title) {
			return iter;
		}
	}
	return shelf.end();
}

int main()
{
	string input;
	size_t pos;
	set<Book> shelf, borrowed, returned;
	while (getline(cin, input)) {
		if (input == "END") break;
		pos = input.find('"', 1);
		Book book(input.substr(0, pos + 1), input.substr(pos + 5));
		shelf.insert(book);
	}
	while (getline(cin, input)) {
		if (input == "END") break;
		pos = input.find(' ');
		string cmd(input.substr(0, pos)), title(input.substr(pos + 1));
		if (cmd[0] == 'B') {
			set<Book>::iterator iter = SearchBookByTitle(shelf, title);
			if (iter != shelf.end()) {
				borrowed.insert(*iter);
				shelf.erase(iter);
			}
		}
		else if (cmd[0] == 'R') {
			set<Book>::iterator iter = SearchBookByTitle(borrowed, title);
			if (iter != borrowed.end()) {
				returned.insert(*iter);
				borrowed.erase(iter);
			}
		}
		else if (cmd[0] == 'S') {
			for (const Book &book : returned)
			{
				cout << "Put " << book.title;
				auto iter = shelf.lower_bound(book);
				if (iter == shelf.begin()) {
					cout << " first" << endl;
				}
				else {
					cout << " after " << (--iter)->title << endl;
				}
				shelf.insert(book);
			}
			returned.clear();
			cout << "END" << endl;
		}
		else;
	}
	return 0;
}
/*
"The Canterbury Tales" by Chaucer, G.
"Algorithms" by Sedgewick, R.
"The C Programming Language" by Kernighan, B. and Ritchie, D.
END
BORROW "Algorithms"
BORROW "The C Programming Language"
RETURN "Algorithms"
RETURN "The C Programming Language"
SHELVE
END
*/