题意分析

题目模拟图书馆书籍管理系统，要求根据借书、还书和上架指令，输出每本归还书籍应放置的位置。初始时所有书籍按作者和书名排序放在书架上，借阅时从书架移除，归还时暂存总服务台，收到上架指令时按排序规则将暂存书籍放回书架。需注意：1）排序优先级为作者名＞书名（ASCII顺序）；2）输出格式需指明每本书应放在哪本书之后，若为第一本则输出"first"。

解题思路

代码使用set和map数据结构实现高效查询和排序：1）用map存储书名到书籍信息的映射，便于快速查找；2）用两个set分别维护书架上的书（lib）和总服务台的书（desk），通过自定义比较函数（作者降序、书名降序）实现升序排序；3）上架时遍历desk中的书，利用upper_bound找到当前书应插入的位置，输出放置指令并更新lib；4）处理BORROW、RETURN和SHELVE指令时，通过map和set的组合操作实现O(log n)时间复杂度的查询和修改。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <string> 
using namespace std;
struct book {
	string title;
	string author;
};
bool operator<(const book& a, const book& b)
{
	if (a.author == b.author)
	{
		return a.title > b.title; 
	}
	else
	{
		return a.author > b.author;
	}
}
set<book> lib;
set<book> desk;
map<string, book> mp;
int main()
{
	//freopen("1886.txt","r",stdin); 
	string s;
	while (getline(cin, s), s != "END")
	{
		//cout<<s<<endl;
		int pos = s.find(" by ");
		string title = s.substr(0, pos);
		string author = s.substr(pos + 4);
		book shu;
		shu.title = title;
		shu.author = author;
		mp[title] = shu;
		lib.insert(shu);
	}
	while (getline(cin, s), s != "END")
	{
		if (s.substr(0, 6) == "BORROW")
		{
			//cout<<"hi0"<<endl;
			string title = s.substr(7);
			lib.erase(mp[title]);
		}
		else if (s.substr(0, 6) == "RETURN")
		{
			//cout<<"hi1"<<endl;			
			string title = s.substr(7);
			desk.insert(mp[title]);
		}
		else
		{
			//cout<<"hi2"<<endl;			
			for (set<book>::reverse_iterator it = desk.rbegin(); it != desk.rend(); it++)
			{
				cout << "Put " << it->title;
				if (lib.upper_bound(*it) == lib.end())
				{
					cout << " first" << endl;
				}
				else
				{
					cout << " after " << lib.upper_bound(*it)->title << endl;
				}
				lib.insert(*it);
			}
			cout << "END" << endl; 
			desk.clear();
		}
	}
	return 0;
}