数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中配对链的最大长度
假设在 Dota2 的世界中，有两个阵营——天辉和夜魇。Dota2 议会由来自这两个阵营的议员组成。现在，议会希望对 Dota2 游戏进行一些修改。对这些修改的投票是一个基于轮次的程序。在每一轮中，每个议员可以行使以下两种权利之一：
禁止一名议员的权利——一名议员可以使另一名议员在此轮及所有后续轮次中失去所有权利。
宣布胜利——如果这名议员发现仍然有权投票的议员都来自同一阵营，他可以宣布胜利并做出关于游戏修改的决定。
给定一个字符串，表示每个议员所属的阵营。字符 'R' 和 'D' 分别代表天辉阵营和夜魇阵营。然后，如果有 n 名议员，则给定字符串的长度将为 n。
基于轮次的程序从给定顺序中的第一名议员到最后一名议员开始。此程序将持续到投票结束。所有失去权利的议员都将在程序中被跳过。
假设每个议员都足够聪明，并且可以为自己的阵营采取最佳策略，您需要预测哪个阵营最终将宣布胜利并对 Dota2 游戏进行修改。输出应为天辉或夜魇。
因此，如果输入类似于“RDD”，则输出将为夜魇。这是因为第一名议员来自天辉，他可以在第 1 轮中禁止下一名议员的权利。第二名议员将无法再行使任何权利，因为他的权利已被禁止。之后，第三名议员来自夜魇，他可以在第 1 轮中禁止第一名议员的权利。现在在第 2 轮中，第三名议员可以宣布胜利，因为他是在议会中唯一可以投票的人。
为了解决这个问题，我们将遵循以下步骤：
创建一个队列 q1、q2，n := 字符串的长度。对于所有 R，将其插入 q1，对于所有 D，将其插入 q2。
当两个队列都不为空时
如果 q1 的前部元素 < q2 的前部元素，则
将 n 插入 q1，从 q2 和 q1 中删除
否则，将 n 插入 q2，从 q2 和 q1 中删除
将 n 加 1
如果队列为空，则返回夜魇，否则返回天辉
示例（C++）
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string predictPartyVictory(string s) {
queue <int> q1, q2;
int n = s.size();
for(int i = 0; i < s.size(); i++){
if(s[i] == 'R'){
q1.push(i);
} else {
q2.push(i);
}
}
while(q1.size() && q2.size()){
if(q1.front() < q2.front()){
q1.push(n);
q2.pop();
q1.pop();
} else {
q2.push(n);
q2.pop();
q1.pop();
}
n++;
}
return q1.empty()? "Dire" : "Radiant";
}
};
main(){
Solution ob;
cout <<(ob.predictPartyVictory("RDD"));
}输入
"RDD"
输出
Dire
101 次查看
