---

0649. Dota2 参议院

• 标签：贪心、队列、字符串
• 难度：中等

题目链接

• 0649. Dota2 参议院 - 力扣

题目大意

描述：

Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

• 禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
• 宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。

给定一个字符串 $senate$ 代表每个参议员的阵营。字母 'R' 和 'D' 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 $n$ 个参议员，给定字符串的大小将是 $n$。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

要求：

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire"。

说明：

• $n == senate.length$。
• $1 \le n \le 10^{4}$。
• $senate[i]$ 为 'R' 或 'D'。

示例：

• 示例 1：

输入：senate = "RD"
输出："Radiant"
解释：
第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。
这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。
第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人。

• 示例 2：

输入：senate = "RDD"
输出："Dire"
解释：
第 1 轮时，第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。
这一轮中，第二个来自 Dire 阵营的参议员会将被跳过，因为他的权利被禁止了。
这一轮中，第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

解题思路

思路 1：贪心 + 队列

思路 1：算法描述

这道题目模拟 Dota2 参议院的投票过程。每个参议员都会采取最优策略，即优先禁止对方阵营中最早投票的参议员。

我们可以使用两个队列分别存储 Radiant 和 Dire 阵营参议员的位置索引，然后模拟投票过程。

具体步骤如下：

1. 初始化两个队列 $radiant$ 和 $dire$，分别存储两个阵营参议员的位置索引。
2. 遍历字符串 $senate$，将每个参议员的位置索引加入对应的队列。
3. 模拟投票过程：
   • 当两个队列都不为空时，取出两个队列的队首元素 $r$ 和 $d$。
   • 比较 $r$ 和 $d$ 的大小：
     • 如果 $r < d$，说明 Radiant 阵营的参议员先投票，他会禁止 Dire 阵营的参议员。将 $r + n$（$n$ 是参议员总数）加入 $radiant$ 队列，表示该参议员在下一轮还可以投票。
     • 如果 $r > d$，说明 Dire 阵营的参议员先投票，他会禁止 Radiant 阵营的参议员。将 $d + n$ 加入 $dire$ 队列。
4. 最后，哪个队列不为空，哪个阵营获胜。

思路 1：代码

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        from collections import deque
        
        n = len(senate)
        radiant = deque()  # Radiant 阵营参议员的位置索引
        dire = deque()     # Dire 阵营参议员的位置索引
        
        # 初始化两个队列
        for i, s in enumerate(senate):
            if s == 'R':
                radiant.append(i)
            else:
                dire.append(i)
        
        # 模拟投票过程
        while radiant and dire:
            r = radiant.popleft()
            d = dire.popleft()
            
            # 位置靠前的参议员先投票，禁止对方阵营的参议员
            if r < d:
                # Radiant 阵营的参议员先投票
                radiant.append(r + n)
            else:
                # Dire 阵营的参议员先投票
                dire.append(d + n)
        
        # 判断哪个阵营获胜
        return "Radiant" if radiant else "Dire"

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是参议员的数量。每个参议员最多被处理常数次。
• 空间复杂度：$O(n)$。需要使用两个队列存储参议员的位置索引。