我的思路:
用pair存储书名和作者,map<pair,int>表示映射关系,int的不同取值表示书的状态,这样BORROW时不是移除而是修改int,RETURN时我们需要存储要输出的书名,在S命令里找到他们的位置,这种方法写一半弃疗了感觉很麻烦...但这样不如下面的优化思路方便
优化思路:
先考虑如何输出结果方便,我们需要存储归还的书和保证它们原来的相对顺序不变,很容易想到自动排序的容器,但是如果字符串存储及其查找在map和set有点花时间,
考虑到之前集合栈和数据库的思想,我们可以将字符串数字化,它的数字代表它原来的位置,这样我们设置set这样能按顺序输出内容,还能够去重,避免重复输入,那么就是两个set存储归还的书和图书馆的书.
我们定义map使得id与书名对应,那么接下来考虑如何存储书, 这里结构体和pair应该都可,因为我们用到它只是建立书名和id的连接
排序时不要忘了去掉引号,如果以发送邮件的思想,保存引号应该更方便,但是这样会导致排序错误
1 #include <bits/stdc++.h>
2 using namespace std;
3 struct books{
4 int id;
5 string name,writer;
6 bool operator<(books it){
7 return writer<it.writer||(writer==it.writer&&name<it.name);//括号的优先级
8 }//可以将return内容看成要求 引号相同影响比较,会增加短字符串的长度
9 }bk[12010];
10 set<int> lib,ret;//表示库存,已被借走的书
11 unordered_map<string,int> mbook;
12 int main()
13 {
14 string book,writer,command;int sum = 0;
15 while(getline(cin,book)&&book!="END"){
16 int pos = book.find(" by ");
17 writer = book.substr(pos+4);
18 book = book.substr(1,pos-2);
19 bk[sum].name = book;
20 bk[sum++].writer = writer;
21 }
22 sort(bk,bk+sum);
23 for(int i=0;i<sum;i++) {
24 bk[i].id = i;
25 lib.insert(i);
26 mbook[bk[i].name]=i;//存入id,类似之前的习题集合栈 name-id
27 }
28 while(cin>>command&&command!="END"){
29 if(command[0]=='S'){
30 for(auto it:ret){
31 auto tmp = lib.find(it);
32 if(tmp==lib.begin()) printf("Put \"%s\" first\n",bk[*tmp].name.c_str());
33 else{
34 tmp--;
35 printf("Put \"%s\" after \"%s\"\n",bk[it].name.c_str(),bk[*tmp].name.c_str());
36 }
37 }
38 printf("END\n");
39 ret.clear();
40 continue;
41 }
42 getline(cin,book);
43 book.erase(0,2); book.erase(book.size()-1,1);
44 if(command[0]=='B') lib.erase(mbook[book]);
45 else if(command[0]=='R') {
46 // cout<<book<<endl;
47 ret.insert(mbook[book]);
48 lib.insert(mbook[book]);
49 // printf("插入%d\n",mbook[book]);
50 }
51 }
52 return 0;
53 }