題目描述
Dota2 的世界里有兩個陣營：Radiant(天輝)和 Dire(夜魘)
Dota2 參議院由來自兩派的參議員組成∷δ眨現(xiàn)在參議院希望對一個 Dota2 游戲里的改變作出決定。他們以一個基于輪為過程的投票進(jìn)行牵素。在每一輪中浩考，每一位參議員都可以行使兩項權(quán)利中的一項：
- 禁止一名參議員的權(quán)利：
參議員可以讓另一位參議員在這一輪和隨后的幾輪中喪失所有的權(quán)利疆瑰。 - 宣布勝利：
如果參議員發(fā)現(xiàn)有權(quán)利投票的參議員都是同一個陣營的互站，他可以宣布勝利并決定在游戲中的有關(guān)變化汁展。
給定一個字符串代表每個參議員的陣營鹊碍。字母 “R” 和 “D” 分別代表了 Radiant（天輝）和 Dire（夜魘）。然后食绿，如果有 n 個參議員侈咕，給定字符串的大小將是 n。
以輪為基礎(chǔ)的過程從給定順序的第一個參議員開始到最后一個參議員結(jié)束器紧。這一過程將持續(xù)到投票結(jié)束耀销。所有失去權(quán)利的參議員將在過程中被跳過。
假設(shè)每一位參議員都足夠聰明铲汪，會為自己的政黨做出最好的策略宫纬，你需要預(yù)測哪一方最終會宣布勝利并在 Dota2 游戲中決定改變柠傍。輸出應(yīng)該是 Radiant 或 Dire祟同。
示例 1：
輸入："RD"
輸出："Radiant"
解釋：第一個參議員來自 Radiant 陣營并且他可以使用第一項權(quán)利讓第二個參議員失去權(quán)力焕参，因此第二個參議員將被跳過因為他沒有任何權(quán)利。然后在第二輪的時候齿梁，第一個參議員可以宣布勝利催植，因為他是唯一一個有投票權(quán)的人
示例 2：
輸入："RDD"
輸出："Dire"
解釋：
第一輪中,第一個來自 Radiant 陣營的參議員可以使用第一項權(quán)利禁止第二個參議員的權(quán)利
第二個來自 Dire 陣營的參議員會被跳過因為他的權(quán)利被禁止
第三個來自 Dire 陣營的參議員可以使用他的第一項權(quán)利禁止第一個參議員的權(quán)利
因此在第二輪只剩下第三個參議員擁有投票的權(quán)利,于是他可以宣布勝利
提示：
給定字符串的長度在 [1, 10,000] 之間.
解題思路
- 貪心
如果當(dāng)前參議院有權(quán)利，那么選按照投票順序的下一名敵對的議員，使其喪失權(quán)利查邢，這樣他便不能對我方造成損失蔗崎。
由于我們總要挑選投票順序最早的議員，因此我們可以使用兩個隊列分別按照投票順序存儲天輝方和夜魘方每一名議員的投票時間扰藕。隨后我們就可以開始模擬整個投票的過程：
如果此時 某一方為空缓苛，那么就可以宣布另一方獲得勝利；
如果均不為空邓深，那么比較這兩個隊列的首元素未桥，就可以確定當(dāng)前行使權(quán)利的是哪一名議員。如果某方隊列的首元素較小芥备，那說明該方的議員行使權(quán)利冬耿，其會挑選對方的首元素對應(yīng)的那一名議員。因此萌壳，我們會將敵方元素永久地彈出亦镶，并將該方的首元素彈出，增加 n 之后再重新放回隊列袱瓮，這里 n 是給定的字符串 senate 的長度缤骨，即表示該議員會參與下一輪的投票。
作者：LeetCode-Solution
源碼
class Solution {
public:
string predictPartyVictory(string senate) {
int n=senate.length();
queue<int> D,R;
for(int i=0;i<n;i++)
{
if(senate[i]=='R')
{
R.push(i);
}
else
{
D.push(i);
}
}
while(!D.empty()&&!R.empty())
{
int D_front=D.front();
int R_front=R.front();
if(D_front>R_front)
{
R.push(R_front+n);
}
else
{
D.push(D_front+n);
}
D.pop();
R.pop();
}
if(D.empty())return "Radiant";
else return "Dire";
}
};
題目來源
來源：力扣（LeetCode）
