P9518 queue 题解。

1. 题解

我们可以用 list 模拟队列，在更新队列的同时维护一个 unordered_map 记录元素出现的位置。

为了方便，我们用 \(\mathrm{A1}\) 表示排队队列，\(\mathrm{A2}\) 表示游玩队列。

对于操作 start，先将 \(\mathrm{A2}\) 的元素放入 \(\mathrm{A1}\) 的队尾，然后将 \(\mathrm{A1}\) 队头的元素放入 \(\mathrm{A2}\)，如果 \(\mathrm{A1}\) 为空则输出 Error。

while (!A2.empty()) {
    string x = A2.front();
    A2.pop_front();
    S2.erase(x);
    A1.push_back(x);
    S1[x] = --A1.end();
}
if (A1.empty()) {
    cout << "Error\n";
    continue;
}
int cnt = 0;
while (!A1.empty() && cnt < 2) {
    string x = A1.front();
    A1.pop_front();
    S1.erase(x);
    A2.push_back(x);
    S2[x] = --A2.end(), ++cnt;
    cout << x << ' ';
}
cout << '\n';

对于操作 arrive，如果 \(x\) 在 \(\mathrm{A1}\) 或 \(\mathrm{A2}\) 中则输出 Error，否则将 \(x\) 放到 \(\mathrm{A1}\) 的队尾，并输出 OK。

if (S1.contains(x) || S2.contains(x)) {
    cout << "Error\n";
    continue;
}
A1.push_back(x);
S1[x] = --A1.end();
cout << "OK\n";

对于操作 leave，如果 \(x\) 不在 \(\mathrm{A1}\) 中则输出 Error，否则根据记录的位置将 \(x\) 在 \(\mathrm{A1}\) 删除，并输出 OK。

if (!S1.contains(x)) {
    cout << "Error\n";
    continue;
}
A1.erase(S1[x]);
S1.erase(x);
cout << "OK\n";

2. Code

#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
int n;
string op;
list<string> A1, A2;
unordered_map<string, list<string>::iterator> S1, S2;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    while (n--) {
        cin >> op;
        if (op == "start") {
            while (!A2.empty()) {
                string x = A2.front();
                A2.pop_front();
                S2.erase(x);
                A1.push_back(x);
                S1[x] = --A1.end();
            }
            if (A1.empty()) {
                cout << "Error\n";
                continue;
            }
            int cnt = 0;
            while (!A1.empty() && cnt < 2) {
                string x = A1.front();
                A1.pop_front();
                S1.erase(x);
                A2.push_back(x);
                S2[x] = --A2.end(), ++cnt;
                cout << x << ' ';
            }
            cout << '\n';
        } else if (op == "arrive") {
            string x;
            cin >> x;
            if (S1.contains(x) || S2.contains(x)) {
                cout << "Error\n";
                continue;
            }
            A1.push_back(x);
            S1[x] = --A1.end();
            cout << "OK\n";
        } else {
            string x;
            cin >> x;
            if (!S1.contains(x)) {
                cout << "Error\n";
                continue;
            }
            A1.erase(S1[x]);
            S1.erase(x);
            cout << "OK\n";
        }
    }
    return 0;
}