POJ 1281 - MANAGER

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

概要

優先順位付きキューのようなものを考え，以下の3種類のクエリを処理する．

このとき，「i 回目の削除クエリで取り除かれた要素のコストは何か」というクエリがいくつかあるので，それに答える．

ただし，削除クエリがきたときにキューが空のときは，-1 を取り除いたこととする．

制約

解法

コストの種類が多くないので，ビンソートのようにデータを持って，削除クエリのときに順方向・逆方向に走査して削除する要素を探す．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (scanf("%d", &N) != EOF) {
 9     int M;
10     scanf("%d", &M);
11     vector<int> req(M);
12     for (int i = 0; i < M; i++) {
13       scanf("%d", &req[i]);
14       --req[i];
15     }
16 
17     vector<int> removed;
18     vector<int> bin(N, 0);
19     int policy = 1;
20     for (char cmd; scanf("%c", &cmd) != EOF && cmd != 'e';) {
21       switch (cmd) {
22         case 'a':
23           {
24             int x;
25             scanf("%d", &x);
26             ++bin[x-1];
27           }
28           break;
29         case 'r':
30           {
31             int p = -1;
32             if (policy == 1) {
33               for (int i = 0; i < N; i++) {
34                 if (bin[i] > 0) {
35                   p = i;
36                   --bin[i];
37                   break;
38                 }
39               }
40             } else {
41               for (int i = N-1; i >= 0; i--) {
42                 if (bin[i] > 0) {
43                   p = i;
44                   --bin[i];
45                   break;
46                 }
47               }
48             }
49             removed.push_back(p);
50           }
51           break;
52         case 'p':
53           scanf("%d", &policy);
54           break;
55       }
56     }
57     for (int i = 0; i < M; i++) {
58       printf("%d\n", removed[req[i]]+1);
59     }
60     puts("");
61   }
62   return 0;
63 }
poj/1281.cc