27925: 小组队列

http://cs101.openjudge.cn/practice/27925/

有 n个小组要排成一个队列，每个小组中有若干人。当一个人来到队列时，如果队列中已经有了自己小组的成员，他就直接插队排在自己小组成员的后面，否则就站在队伍的最后面。请你编写一个程序，模拟这种小组队列。

注意：每个人的编号不重复，另外可能有散客。

输入

第一行：小组数量 t (t<100)。接下来 t 行，每行输入一个小组描述，表示这个小组的人的编号。编号是 0 到 999999 范围内的整数，一个小组最多可包含 1000 个人。最后，命令列表如下。有三种不同的命令： 1、ENQUEUE x - 将编号是 x 的人插入队列； 2、DEQUEUE - 让整个队列的第一个人出队； 3、STOP - 测试用例结束每个命令占一行，不超过50000行。

输出

对于每个 DEQUEUE 命令，输出出队的人的编号，每个编号占一行。

样例输入

Sample1 input:
2
101 102 103
201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP

Sample1 output:
101
102
103
201
202
203

样例输出

Sample2 input:
2
259001 259002 259003 259004 259005
260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP

Sample2 output:
259001
259002
259003
259004
259005
260001

来源

acwing 小组队列 https://www.acwing.com/problem/content/description/134/

这题是 Team Queue / 小组队列，不能把所有人放一个队列，因为插队规则是“排在本组最后一个人后面”，因此：核心思路（经典做法）

用一个 dict：member → group_id 每个人属于哪个组。
用一个 deque：group_queue 记录哪些组当前在队列中，以及它们的顺序。
用一个 dict：group → deque of members 保存该组当前队列里的成员顺序。
ENQUEUE x
- 找到 x 的组 g
- 如果该组当前不在总队列中，则把 g 加入 group_queue
- 把 x 加入 group_members[g]
DEQUEUE
- 找 group_queue 的第一个组 g
- 弹出 group_members[g] 的第一个人
- 如果这个组空了，把它从 group_queue 中移除

时间复杂度：所有操作都是 O(1)，非常快，可以轻松通过 5 万行操作。

python

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())
group_of = {}
for gid in range(t):
    for x in map(int, input().split()):
        group_of[x] = gid   # 记录每个人所属的组

group_queue = deque()       # 当前排队的组顺序
group_members = {}          # 每组自己的队列
in_queue = set()            # 当前有哪些组在 group_queue 中

while True:
    cmd = input().strip()
    if cmd == "STOP":
        break

    if cmd.startswith("ENQUEUE"):
        _, x = cmd.split()
        x = int(x)
        g = group_of.get(x, -1)   # -1 表示散客

        if g not in in_queue:
            in_queue.add(g)
            group_queue.append(g)
            group_members[g] = deque()

        group_members[g].append(x)

    else:  # DEQUEUE
        g = group_queue[0]
        x = group_members[g].popleft()
        print(x)

        if not group_members[g]:  # 该组没人了，移除该组
            group_queue.popleft()
            in_queue.remove(g)

python

from collections import deque					# 时间: 105ms

# Initialize groups and mapping of members to their groups
t = int(input())
groups = {}
member_to_group = {}



for _ in range(t):
    members = list(map(int, input().split()))
    group_id = members[0]  # Assuming the first member's ID represents the group ID
    groups[group_id] = deque()
    for member in members:
        member_to_group[member] = group_id

# Initialize the main queue to keep track of the group order
queue = deque()
# A set to quickly check if a group is already in the queue
queue_set = set()


while True:
    command = input().split()
    if command[0] == 'STOP':
        break
    elif command[0] == 'ENQUEUE':
        x = int(command[1])
        group = member_to_group.get(x, None)
        # Create a new group if it's a new member not in the initial list
        if group is None:
            group = x
            groups[group] = deque([x])
            member_to_group[x] = group
        else:
            groups[group].append(x)
        if group not in queue_set:
            queue.append(group)
            queue_set.add(group)
    elif command[0] == 'DEQUEUE':
        if queue:
            group = queue[0]
            x = groups[group].popleft()
            print(x)
            if not groups[group]:  # If the group's queue is empty, remove it from the main queue
                queue.popleft()
                queue_set.remove(group)

27925: 小组队列 ​

27925: 小组队列