Dota 2 Senate解题时如何避免遍历中修改列表的陷阱并实现高效模拟策略

Dota 2 Senate题目要求模拟参议院投票过程，每个参议员可以行使权利禁止同阵营的其他参议员后续投票，直到所有剩余参议员属于同一阵营。很多开发者第一反应是用列表存储参议员状态，在遍历过程中直接修改列表，但这种方式很容易引发问题。

遍历中修改列表的常见陷阱

如果使用列表存储参议员阵营，在遍历过程中直接删除被禁止的参议员，会导致列表长度变化，后续索引对应不上原来的参议员顺序，出现漏判或者误判的情况。比如初始列表是R,R,D,D，遍历到第一个R时删除了后面的D，列表长度变为3，下一个遍历索引指向的是原来的第三个元素，已经被跳过，导致模拟逻辑错误。

下面是错误的代码示例，直接在遍历中修改列表：

senators = list("RDDDR")
n = len(senators)
for i in range(n):
    # 遍历过程中修改列表，会导致索引错乱
    if senators[i] == "R":
        # 找到第一个D并删除
        for j in range(i+1, len(senators)):
            if senators[j] == "D":
                del senators[j]
                break
print(senators)

高效模拟策略：队列+贪心

正确的解法可以使用两个队列分别存储R和D参议员的初始索引，因为投票是按顺序循环的，索引越小的参议员越早行使权利。每次比较两个队列的队首元素，索引小的参议员获胜，将其索引加上总人数后重新加入队列尾部，代表下一轮可以继续投票；索引大的参议员直接出队，相当于被禁止。直到其中一个队列为空，剩下的队列对应的阵营获胜。

核心逻辑说明

• 用两个队列分别记录R和D参议员的原始位置索引，保证投票顺序和原始顺序一致
• 每次比较两个队列的第一个元素，索引小的参议员胜出，胜出的参议员索引加上总人数后入队，代表进入下一轮投票
• 索引大的参议员直接出队，不再参与后续投票
• 当其中一个队列为空时，另一个队列对应的阵营获胜

完整代码实现

以下是Python语言的完整实现代码：

from collections import deque

def predictPartyVictory(senate):
    n = len(senate)
    # 分别存储R和D的索引
    r_queue = deque()
    d_queue = deque()
    # 初始化队列，记录每个参议员的原始位置
    for i, ch in enumerate(senate):
        if ch == "R":
            r_queue.append(i)
        else:
            d_queue.append(i)
    # 循环模拟投票过程
    while r_queue and d_queue:
        r_idx = r_queue.popleft()
        d_idx = d_queue.popleft()
        # 索引小的胜出，加入下一轮
        if r_idx < d_idx:
            r_queue.append(r_idx + n)
        else:
            d_queue.append(d_idx + n)
    # 判断哪个队列还有元素
    return "Radiant" if r_queue else "Dire"

# 测试示例
print(predictPartyVictory("RD"))  # 输出Radiant
print(predictPartyVictory("RDD"))  # 输出Dire

策略优势分析

这种队列模拟的方式时间复杂度是O(n)，每个参议员最多入队出队一次，不会出现遍历修改列表的索引问题。同时用索引加总的方式处理循环投票，不需要额外维护轮次变量，逻辑简洁且不容易出错。对于类似的循环淘汰类模拟题，都可以参考这种队列+贪心的思路，避免直接修改遍历容器的陷阱。

注意队列中存储的是原始索引，加上总人数后可以保证下一轮的索引仍然大于当前轮所有未处理的索引，保证投票顺序的正确性。

Dota_2_Senate遍历修改列表陷阱队列模拟循环队列贪心策略修改时间：2026-06-17 06:24:21