題目： UVa - 12207 - That is Your Queue

題目說明

給兩個數字，P、C，P 代表列表中的序號個數，從 1 開始，一開始的排序為升冪排序，例如 P = 3 則列表為 {1, 2, 3}。C 代表接下來有幾行指令，若指令為 N 表示輸出列表最前面的序號並且將此序號移到列表的尾端，若為 E 加上一個序號代表將該序號代表將該序號移到列表的前端。

解題思路

使用 List 模擬操作並且使用 Unordered_map 提升搜尋速度即可。需要注意的是，若 C 的值小於 P 的值則我們一開始只需要推入 C 個序號即可，因為後面的序號除非被往前移動，否則絕對不會使用到。

參考解法

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
#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int main()
{
    char ch;
    int P, C, tmp, Case = 0;
    list<int> l;
    unordered_map<int, list<int>::iterator> m;
    while (cin >> P >> C && (P || C))
    {
        l.clear(), m.clear();
        cout << "Case " << ++Case << ":\n";
        for (int i = 1; i <= min(P, C); i++) m[i] = l.insert(l.end(), i);
        while (C--)
        {
            cin >> ch;
            if (ch == 'N')
            {
                cout << l.front() << '\n';
                m[l.front()] = l.insert(l.end(), l.front());
                l.pop_front();
            }
            else if (ch == 'E')
            {
                cin >> tmp;
                if (m.find(tmp) != m.end()) l.erase(m[tmp]);
                m[tmp] = l.insert(l.begin(), tmp);
            }
        }
    }
}