一个不错的队列套队列模拟题。

思路

1. 开一个包含 $T$ 个队列的数组 $Q$。其中，$Q_0$ 表示所有小团队在整个大队列当中的排队顺序。$Q_1 - Q_t$ 表示 $t$ 个小团队内部的排队顺序。

2. 入队时，将该成员 push 进其所属的小团队队列当中去。如果小队列当中只有一个人，则表示他是该团队第一个排队成员，将团队 push 到 $Q_0$ 当中。

3. 出队时，把第一个团队的第一个成员出队。出队后如果该小团队大小为零，则表示他是最后一个该团队的成员。在 $Q_0$ 中把该团队 pop 掉。

核心代码

const int T = 1000 + 5;
int t;
std::queue<int> q[T];
std::map<int, int> belong; // 使用 std::map 存储该成员所属团队编号。时间效率低，空间效率高。

void solution() {
    belong.clear();
    rep(i, 0, T - 1) while (!q[i].empty()) q[i].pop(); // 清空上次的数据
    rep(i, 1, t) {
        int n = read();
        rep(j, 1, n) {
            int num = read();
            belong[num] = i; 
        }
    }
    std::string s; while (std::cin >> s && s != "STOP") {
        if (s == "ENQUEUE") {
            int num = read();
            q[belong[num]].push(num); // 在该团队末尾排队
            if (q[belong[num]].size() == 1) q[0].push(belong[num]); // 该团队第一人
        } else if (s == "DEQUEUE") {
            int front = q[q[0].front()].front(); q[q[0].front()].pop();
            print(front), puts(""); // 最首位团队的队头出队
            if (q[belong[front]].empty()) q[0].pop(); // 是否需要删掉这个团队
        }
    }
}

// 注意输出格式
int kase = 0; while (std::cin >> t && t) printf("Scenario #%d\n", ++kase), solution(), puts("");