I mean your borrowers of books — those mutilators of collections, spoilers of the symmetry of shelves, and creators of odd volumes. – (Charles Lamb, Essays of Elia (1823) ‘The Two Races of Men’)
Like Mr. Lamb, librarians have their problems with borrowers too. People don’t put books back where they should. Instead, returned books are kept at the main desk until a librarian is free to replace them in the right places on the shelves. Even for librarians, putting the right book in the right place can be very time-consuming. But since many libraries are now computerized, you can write a program to help.
When a borrower takes out or returns a book, the computer keeps a record of the title. Periodically, the librarians will ask your program for a list of books that have been returned so the books can be returned to their correct places on the shelves. Before they are returned to the shelves, the returned books are sorted by author and then title using the ASCII collating sequence. Your program should output the list of returned books in the same order as they should appear on the shelves. For each book, your program should tell the librarian which book (including those previously shelved) is already on the shelf before which the returned book should go.
Input
First, the stock of the library will be listed, one book per line, in no particular order. Initially, they are all on the shelves. No two books have the same title. The format of each line will be:
title" by author
The end of the stock listing will be marked by a line containing only the word:
END
Following the stock list will be a series of records of books borrowed and returned, and requests from librarians for assistance in restocking the shelves. Each record will appear on a single line, in one of the following formats:
BORROW title
RETURN title
SHELVE
The list will be terminated by a line containing only the word:
END
Output
Each time the SHELVE command appears, your program should output a series of instructions for the librarian, one per line, in the format:
Put title1 after title2
or, for the special case of the book being the first in the collection:
Put title first
After the set of instructions for each SHELVE, output a line containing only the word:
END
Assumptions & Limitations:
1. A title is at most 80 characters long.
2. An author is at most 80 characters long.
3. A title will not contain the double quote (") character.
Sample Input
"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
Sample Output
Put "The C Programming Language" after "The Canterbury Tales"
Put "Algorithms" after "The C Programming Language"
END
题目类型：简单字符处理
算法分析：首先将图书的标题和作者读入并分别使用结构体数组存储相应的值并排序，然后分类处理。当输入的命令是”BORROW”时，将相应数据的访问标志is_return置为-1，当命令是”RETURN”时，将相应数据的访问标志is_return置为1，当命令是”SHELVE”时，遍历所有is_return为1的数据，然后按照位置的不同输出相应的信息并把is_return置为0，注意含first语句的输出。下面第一份代码是更好的实现
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 |
/************************************************** filename :h.cpp author :maksyuki created time :2018/1/23 22:53:35 last modified :2018/1/24 8:04:15 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; struct node { string na, tit; int is_borrowed; node () {} node (string ttt, string nnn, int iii): tit(ttt), na(nnn), is_borrowed(iii) {} bool operator <(const node &a) const { if(na != a.na) return na < a.na; return tit < a.tit; } }; vector<node> aa; map<string, string> ma; int main() { #ifdef LOCAL CFF; //CFO; #endif string s, sa, sb; while(getline(cin, s)) { if(s == "END") break; sa = s.substr(1, s.find("by") - 3); sb = s.substr(s.find("by") + 1, s.size()); aa.emplace_back(node(sa, sb, false)); ma[sa] = sb; } sort(aa.begin(), aa.end()); stringstream ss; vector<node> ans; while(getline(cin, s)) { if(s == "END") break; for(int i = 0; s[i]; i++) if(s[i] == '\"') s[i] = ' '; ss.clear(), ss << s; ss >> sa; if(sa == "BORROW") { string sc; bool is_first = true; while(ss >> sc) { if(is_first) { is_first = false; sb = sc; } else sb += " " + sc; } int len = aa.size(); for(int i = 0; i < len; i++) { if(aa[i].tit == sb) { aa[i].is_borrowed = true; break; } } } if(sa == "RETURN") { string sc; bool is_first = true; while(ss >> sc) { if(is_first) { is_first = false; sb = sc; } else sb += " " + sc; } ans.emplace_back(node(sb, ma[sb], false)); } if(sa == "SHELVE") { sort(ans.begin(), ans.end()); int alen = ans.size(), len = aa.size(), pos = -1; for(int i = 0; i < alen; i++) { for(int j = 0; j < len; j++) if(ans[i].na == aa[j].na) { pos = j; break; } bool is_returned = false; for(int j = pos - 1; j >= 0; j--) if(!aa[j].is_borrowed) { cout << "Put \"" << ans[i].tit << "\" after "; cout << "\"" << aa[j].tit << "\"" << endl; is_returned = true; break; } if(!is_returned) cout << "Put \"" << ans[i].tit << "\" first" << endl; aa[pos].is_borrowed = false; } ans.clear(); cout << "END" << endl; } } return 0; } |
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 |
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> using namespace std; #define EPS 1e-8; const int maxn = 88 + 8; struct point { char tit[maxn]; char aut[maxn]; short is_return; }; point ans[166666]; int len = 0; bool Cmp (point a, point b) { if (strcmp (a.aut, b.aut)) { if (strcmp (a.aut, b.aut) < 0) return true; return false; } else if (strcmp (a.tit, b.tit)) { if (strcmp (a.tit, b.tit) < 0) return true; return false; } return false; } int Search (char *val) { int i; for (i = 0; i < len; i++) if (!strcmp (val, ans[i].tit)) return i; return -1; } int FindPos (int val) { int i; for (i = val - 1; i >= 0; i--) if (ans[i].is_return == 0) return i; return -1; } int main() { // ifstream cin ("aaa.txt"); // freopen ("aaa.txt", "r", stdin); char input[maxn]; while (cin.getline (input, maxn)) { if (!strcmp (input, "END")) break; int i, j; for (i = 0, j = 0; input[i]; i++, j++) { if (input[i] == '"' && i) break; ans[len].tit[j] = input[i]; } ans[len].tit[j] = '"'; ans[len].tit[j+1] = '\0'; for (j = 0, i += 5; input[i]; i++, j++) ans[len].aut[j] = input[i]; ans[len].aut[j] = '\0'; ans[len].is_return = 0; len++; } sort (ans, ans + len, Cmp); char temp[maxn]; while (cin >> input) { if (!strcmp (input, "END")) break; if (!strcmp (input, "BORROW")) { cin.get (); cin.getline (temp, maxn); int val = Search (temp); ans[val].is_return = -1; } else if (!strcmp (input, "RETURN")) { cin.get (); cin.getline (temp, maxn); int val = Search (temp); ans[val].is_return = 1; } else if (!strcmp (input, "SHELVE")) { int i; for (i = 0; i < len; i++) { if (ans[i].is_return == 1) { int weizhi = FindPos (i); if (weizhi == -1) cout << "Put " << ans[i].tit << " first" << endl; else cout << "Put " << ans[i].tit << " after " << ans[weizhi].tit << endl; ans[i].is_return = 0; } } cout << "END" << endl; } } return 0; } |