POJ 3078 - Q

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

概要

m 個の要素を持つキューが与えられる． n 個の starting-position to requested-position という命令が与えられ，starting-position にある要素を requested-position に移動しろということを表す．

これら n 個の命令は同時に実行される．つまり， item1 item2 item3 というキューに対して

という命令がきたら，結果は item2 item3 item1 になる．

制約

解法

命令通りにシミュレーション．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int T;
 8   cin >> T;
 9   while (T-- > 0) {
10     int M, N;
11     cin >> M >> N;
12     vector<int> before(M), after(M);
13     vector<string> v(M);
14     for (int i = 0; i < M; i++) {
15       cin >> v[i];
16       before[i] = i;
17       after[i] = -1;
18     }
19     for (int i = 0; i < N; i++) {
20       int from, to;
21       cin >> from >> to;
22       --from; --to;
23       after[to] = from;
24       before[from] = -1;
25     }
26     for (int i = 0, j = 0; i < M; i++) {
27       if (after[i] == -1) {
28         for (; before[j] == -1; j++);
29         after[i] = j;
30         before[j] = -1;
31       }
32     }
33     for (int i = 0; i < M; i++) {
34       if (i != 0) {
35         cout << ' ';
36       }
37       cout << v[after[i]];
38     }
39     cout << endl;
40   }
41   return 0;
42 }
poj/3078.cc