UVa 230 - Borrowers

题目分析这道题模拟图书馆的图书借还系统。图书馆有一个藏书目录包含每本书的标题和作者。初始时所有书都在书架上。系统需要处理三种操作BORROW title借出指定书名的书RETURN title归还指定书名的书归还的书暂存在一个待上架列表中SHELVE将当前所有归还的书按规则放回书架并输出放置指令图书的排序规则是先按作者名排序作者相同则按书名排序使用ASCII字典序。对于每本归还的书需要找到在排序后的书架上它应该放在哪本书之后。如果它应放在书架的最前面即没有比它更靠前的书在书架上则输出Put title first。解题思路存储书籍信息定义一个结构体存储每本书的索引、书名、作者以及是否被借出。一开始所有书都在书架上所以borrowed初值为false。建立排序索引读取初始藏书目录后按作者 → 书名的规则对书籍数组进行排序。排序后记录每本书在排序数组中的位置索引便于后续查找。映射关系使用一个mapstring, int将书名映射到它在排序数组中的索引方便通过书名快速定位书籍。处理操作BORROW将对应书籍的borrowed标记为true表示该书从书架上被拿走。RETURN将对应书籍的信息保存到returned向量中暂时不上架。SHELVE对returned中的书按规则排序然后依次为每本书寻找它在书架上应放置的位置从该书在排序数组中的位置向前查找找到第一本仍在书架上即borrowed false的书。如果找到输出Put title after pre_title。如果没找到即前面所有书都被借走了输出Put title first。然后将这本书的borrowed标记为false放回书架。每次SHELVE结束后清空returned向量并输出END。输入终止当遇到单独的END行时整个程序结束。代码实现// Borrowers// UVa ID: 230// Verdict: Accepted// Submission Date: 2016-05-14// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 定义书籍结构体structbook{intindex;// 在排序数组中的位置索引boolborrowed;// 是否已被借出string title,author;// 书名和作者// 重载小于运算符用于排序先按作者排序作者相同按书名排序booloperator(book x)const{if(author!x.author)returnauthorx.author;elsereturntitlex.title;}};vectorbookbooks,returned;// books: 所有书籍returned: 待上架书籍intmain(){string line;// 读取初始藏书目录直到遇到 ENDwhile(getline(cin,line)line!END){// 查找书名结束的引号位置intindexline.find(\,1);// 提取书名位于第一个引号之后第二个引号之前string titleline.substr(1,index-1);// 提取作者位于第二个引号之后跳过 by 共5个字符string authorline.substr(index5);book aBook;aBook.titletitle;aBook.authorauthor;books.push_back(aBook);}// 按作者和书名排序sort(books.begin(),books.end());// 建立书名到排序后索引的映射mapstring,intindexer;for(inti0;ibooks.size();i){books[i].indexi;books[i].borrowedfalse;indexer.insert(make_pair(books[i].title,i));}// 处理后续的操作命令while(getline(cin,line)line!END){// 借书操作if(line[0]B){string titleline.substr(8,line.length()-9);books[indexer[title]].borrowedtrue;}// 还书操作elseif(line[0]R){string titleline.substr(8,line.length()-9);returned.push_back(books[indexer[title]]);}// 上架操作else{// 将要上架的书籍按规则排序sort(returned.begin(),returned.end());// 依次处理每本待上架的书for(inti0;ireturned.size();i){boolfoundfalse;// 从该书在排序数组中的位置向前查找找到第一本仍在书架上的书for(intjreturned[i].index;j0;j--)if(books[j].borrowedfalse){coutPut \returned[i].title\ after \;coutbooks[j].title\endl;foundtrue;break;}// 如果前面没有书在书架上则放在最前面if(foundfalse)coutPut \returned[i].title\ firstendl;// 将该书标记为已上架books[returned[i].index].borrowedfalse;}// 输出本次 SHELVE 结束标记coutENDendl;// 清空待上架列表returned.clear();}}return0;}