M30874: 匹配队友

queue, http://cs101.openjudge.cn/practice/30874/

在某MMORPG游戏的地下城系统中，一个标准小队由 1 名坦克 (T, Tank)、1 名治疗 (H, Healer) 和 3 名输出 (D, DPS) 组成。假设其按照一种简单的方式匹配随机地下城队友：玩家按先后顺序进入匹配队列。每当队列中的剩余玩家满足上述职责要求时，系统会立即从队列中挑选出最早进入匹配的 5 名符合条件的玩家组成一支队伍。现给定某时刻的匹配队列，输出每位玩家所属的队伍编号。若有玩家未能成功组队，其队伍编号输出为 0。

输入

第一行一个整数 N (1 <= N <= 10^5)。第二行 N 个字符，由 T, H, D 组成，用空格隔开。

输出

一行由空格隔开的 N 个整数。

样例输入

Sample input 1:
10
D D T D H T D D H D
Sample input 2:
6
T H D D D T

样例输出

Sample output 1:
1 1 1 1 1 2 2 2 2 2
Sample output 2:
1 1 1 1 1 0

提示：queue, implementation

来源：2026 spring TA-lxy

这是一个典型的队列模拟问题。由于需要按照玩家进入队列的先后顺序来组队，可以使用双端队列（collections.deque）来分别存储坦克（T）、治疗（H）和输出（D）这三种职责的玩家在原输入中的索引。

解题思路

初始化数据结构：
- 使用三个队列 T_q、H_q、D_q 分别记录对应职责玩家的索引。
- 使用一个长度为 $N$ 的数组 ans 来存储每位玩家最终的队伍编号，初始值全部设为 0。
- 使用一个变量 team_count 记录当前已组建的队伍数量（从 1 开始）。
顺序遍历玩家：
- 依次读入每位玩家，将其索引加入对应职责的队列中。
- 每次加入新玩家后，检查是否满足组队条件：即 T_q 至少有 1 个元素，H_q 至少有 1 个元素，且 D_q 至少有 3 个元素。
- 如果满足条件，说明可以组建一支新队伍：
  - team_count 自增 1。
  - 从 T_q 中取出最先进入的 1 个索引，从 H_q 取出 1 个，从 D_q 取出 3 个。
  - 将这 5 个索引在 ans 数组中对应的值更新为当前的 team_count。
输出结果：
- 遍历结束后，ans 数组中未成功组队玩家的值保持为 0，其余则是对应的队伍编号。

Python 代码实现

python

import sys
from collections import deque


def solve():
    # 使用 sys.stdin.read 快速读取输入，适合处理 N = 10^5 的情况
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    players = input_data[1:]

    # 初始化存储结果的数组，未组队默认为 0
    ans = [0] * N

    # 定义三个队列存储不同职责玩家的索引
    T_q = deque()
    H_q = deque()
    D_q = deque()

    team_count = 0

    for i in range(N):
        role = players[i]
        if role == "T":
            T_q.append(i)
        elif role == "H":
            H_q.append(i)
        elif role == "D":
            D_q.append(i)

        # 检查是否满足组队条件：1 T, 1 H, 3 D
        if len(T_q) >= 1 and len(H_q) >= 1 and len(D_q) >= 3:
            team_count += 1
            # 取出最早进入队列的 5 名符合条件的玩家
            t_idx = T_q.popleft()
            h_idx = H_q.popleft()
            d1_idx = D_q.popleft()
            d2_idx = D_q.popleft()
            d3_idx = D_q.popleft()

            # 标记他们的队伍编号
            ans[t_idx] = team_count
            ans[h_idx] = team_count
            ans[d1_idx] = team_count
            ans[d2_idx] = team_count
            ans[d3_idx] = team_count

    # 输出结果，以空格分隔
    print(*(ans))


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度： $O (N)$ 。每个玩家的索引最多入队一次、出队一次，队列操作的时间复杂度为 $O (1)$ ，因此整体时间复杂度与 $N$ 呈线性关系，能够高效通过 $N = 10^{5}$ 的测试。
空间复杂度： $O (N)$ 。主要用于存储队列和结果数组 ans。

M30874: 匹配队友 ​

M30874: 匹配队友