POJ 1250 - Tanning Salon

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

概要

N 個の tanning bed を持つ日焼けサロンがある． 客がどのタイミングで来て，どのタイミングで出ていったかが与えられる． 新しく客がきたときにどの tanning bed も空いていないと，その客は店内で空くのを待つことになる． tanning bed が空いたときは，待っている客の中で最も早く来ていた客がその tanning bed に入る．

tanning bed に入ることなく出ていった客が何人いたかを答える．

制約

• 1 <= N <= 20
• 1 <= 客の数 <= 26

解法

実際にシミュレーションして数えるだけ．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   int n;
10   while (cin >> n && n != 0) {
11     string seq;
12     cin >> seq;
13     vector<bool> v(26, false);
14     deque<char> q;
15     int ans = 0;
16     for (string::const_iterator it(seq.begin()); it != seq.end(); ++it) {
17       const char c = *it;
18       if (!v[c-'A']) {
19         // enter
20         v[c-'A'] = true;
21         if (n == 0) {
22           q.push_back(c);
23         } else {
24           n--;
25         }
26       } else {
27         // leave
28         v[c-'A'] = false;
29         const deque<char>::iterator p = find(q.begin(), q.end(), c);
30         if (p == q.end()) {
31           if (q.empty()) {
32             n++;
33           } else {
34             q.pop_front();
35           }
36         } else {
37           q.erase(p);
38           ans++;
39         }
40       }
41     }
42     if (ans) {
43       cout << ans << " customer(s) walked away." << endl;
44     } else {
45       cout << "All customers tanned successfully." << endl;
46     }
47   }
48   return 0;
49 }