「Team Queue」小组队列

题目描述

把 $n$ 个小组的人排成一个队列：新人到来时，若队列里已有同组成员，就插到本组最后一人之后，否则站到队尾。输入：多个测试用例，每个用例先给小组数 $t$ （ $1 \le t \le 1000$ ，读到 $t=0$ 结束），随后 $t$ 行每行先给本组人数再给出成员编号（每组至多 1000 人，编号在 $[0,999999]$ ）；接着是若干命令，ENQUEUE x 表示编号 $x$ 入队、DEQUEUE 表示队首出队、STOP 结束该用例，单用例命令数不超过 $2 \times 10^5$ 。输出：每个用例先输出一行 Scenario #k，之后每条 DEQUEUE 输出出队人的编号占一行，用例结束再补一个空行。样例：小组 $\{101,102,103\}$ 、 $\{201,202,203\}$ ，交错执行 ENQUEUE 101,201,102,202,103,203 后连续出队 6 次，输出依次为 101 102 103 201 202 203（各占一行）。

思路

插入规则保证同组成员在队列中始终连续成块，因此队列只需拆成两层：order 记录各小组块的先后，seats[g] 记录小组 $g$ 内部成员的先后。入队时若本组还不在队列中就先把它压入 order，再把 $x$ 追加到本组队尾；出队时取首组队首，组空则把该组移出 order。用 member[x] 归属表按下标寻址，两级队列都只在队首、队尾操作，故入队出队均为 $O(1)$ 。

参考代码

Python 版：

python

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:16
# update_at: 2026-10-04 12:28

import sys
from collections import deque
from collections.abc import Iterator

GROUP = -1  # member[x] 是 x 的小组下标；-1 表示该编号没有被任何小组收录


def run_case(data: Iterator[bytes], member: list[int], t: int) -> list[str]:
    """跑完一个测试用例，返回该用例要输出的所有行。"""
    # 两级队列：order 存「小组块」的先后，seats[g] 存小组 g 内部成员的先后。
    # 小组一旦进入 order 就不再重复入队，新人只追加到自己小组的 seats 里。
    order: deque[int] = deque()
    seats: list[deque[int]] = [deque() for _ in range(t)]
    out: list[str] = []

    while True:
        command = next(data)
        if command == b"STOP":
            return out

        if command == b"DEQUEUE":
            g = order[0]  # order 非空是题意保证：队列为空时不会要求出队
            out.append(str(seats[g].popleft()))
            if not seats[g]:  # 这个小组的最后一个人走了，小组才离开块序列
                order.popleft()
        else:
            x = int(next(data))
            g = member[x]
            if not seats[g]:  # 组内已经有人在排，新人才挨着自己的组员插队
                order.append(g)
            seats[g].append(x)


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    scenario = 0

    while True:
        t = int(next(data))
        if t == 0:
            break

        # 人数可能为 0，小组描述会退化成孤零零一个数字，所以整份输入按 token 读
        member = [GROUP] * 1000000  # 编号域是 0~999999，直接下标寻址比 dict 快
        for g in range(t):
            size = int(next(data))
            ids = [int(next(data)) for _ in range(size)]
            for x in ids:
                member[x] = g

        scenario += 1
        out.append(f"Scenario #{scenario}")
        out += run_case(data, member, t)
        out.append("")  # 每个测试用例输出结束都补一个空行，含最后一个用例

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:20
 * update_at: 2026-10-06 11:20
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXID = 1000000; // 编号范围 0 ~ 999999
const int MAXT = 1005;     // 小组数上限 1000，多开一点

int member[MAXID];      // member[x]：编号 x 所属的小组下标（只存 0~999，用 int 省内存）
queue<ll> seats[MAXT];  // seats[g]：小组 g 内部成员的先后队列，队首是本组最前面的人
queue<ll> order;        // order：当前队列中各个小组块的先后顺序，队首是最前面的小组

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t;          // 小组数量，读到 0 结束
    ll scenario = 0;
    while (cin >> t && t != 0) {
        scenario++;

        for (ll g = 0; g < t; g++) {
            ll size;
            cin >> size;
            for (ll i = 0; i < size; i++) {
                ll x;
                cin >> x;
                member[x] = g;
            }
        }

        // 清空上一用例残留的两级队列
        while (!order.empty()) order.pop();
        for (ll g = 0; g < t; g++) {
            while (!seats[g].empty()) seats[g].pop();
        }

        cout << "Scenario #" << scenario << '\n';

        string command;
        while (cin >> command) {
            if (command == "STOP") break;

            if (command == "DEQUEUE") {
                ll g = order.front(); // 队列非空是题意保证：为空时不会要求出队
                ll x = seats[g].front();
                seats[g].pop();
                cout << x << '\n';
                if (seats[g].empty()) order.pop(); // 本组最后一人走了，小组块才离开块序列
            } else { // ENQUEUE
                ll x;
                cin >> x;
                ll g = member[x];
                if (seats[g].empty()) order.push(g); // 本组还不在队伍里，把小组块压到队尾
                seats[g].push(x);                    // 否则直接接在本组最后一人后面
            }
        }

        cout << '\n'; // 每个用例（含最后一个）末尾都补一个空行
    }

    return 0;
}