POJ 1886 - Borrowers

http://poj.org/problem?id=1886

概要

本棚に本が一列に (著者, 題名) の順にソートされて並んでいる。 この状態から、以下の3つの操作を行う。

• BORROW 与えられた題名の本を本棚から取り出す。
• RETURN 与えられた題名の本を机の上に返す。
• SHELVE 机の上にある本を、左側にくるべき本から順に本棚へ戻す。このとき、戻す本の題名と、戻す位置のすぐ左側にある本の題名を出力する。

制約

• 題名、著者はそれぞれ80文字以内で、ダブルクオートを含まない
• 同じ題名の本は存在しない

解法

本棚の本をソートして、lower_bound で位置を求めて erase したり insert したりする。

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 pair<string, string> parse(const string& line)
 8 {
 9   string::const_iterator it = line.begin();
10   if (*it != '"') {
11     throw "err1";
12   }
13   for (++it; *it != '"'; ++it);
14   const string title(line.begin(), it+1);
15   const string author(it+5, line.end());
16   return make_pair(author, title);
17 }
18 
19 int main()
20 {
21   ios::sync_with_stdio(false);
22   vector<pair<string, string> > shelf;
23   map<string, string> dict;
24   for (string line; getline(cin, line) && line != "END";) {
25     const pair<string, string> r = parse(line);
26     shelf.push_back(r);
27     dict.insert(make_pair(r.second, r.first));
28   }
29   sort(shelf.begin(), shelf.end());
30 
31   vector<pair<string,string> > desk;
32   for (string line; getline(cin, line) && line != "END";) {
33     const string cmd = line.substr(0, 6);
34     if (cmd == "SHELVE") {
35       sort(desk.begin(), desk.end());
36       for (vector<pair<string,string> >::const_iterator it = desk.begin(); it != desk.end(); ++it) {
37         vector<pair<string,string> >::iterator jt = lower_bound(shelf.begin(), shelf.end(), *it);
38         if (jt == shelf.begin()) {
39           cout << "Put " << it->second << " first" << endl;
40         } else {
41           cout << "Put " << it->second << " after " << (jt-1)->second << endl;
42         }
43         shelf.insert(jt, *it);
44       }
45       desk.clear();
46       cout << "END" << endl;
47     } else {
48       const string title = line.substr(7, line.size()-7);
49       const pair<string, string> r = make_pair(dict[title], title);
50       if (cmd == "BORROW") {
51         vector<pair<string,string> >::iterator it = lower_bound(shelf.begin(), shelf.end(), r);
52         shelf.erase(it);
53       } else {
54         desk.push_back(r);
55       }
56     }
57   }
58   return 0;
59 }