LeetCode Dota2 Senate In the world of Dota2, there are two parties: the Radiant and the Dire. The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

1. Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
2. Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.

Given a string representing each senator’s party belonging. The character ‘R’ and ‘D’ represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n. The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure. Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire. Example 1:

Input: "RD"
Output: "Radiant"
Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights any more since his right has been banned.
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

Input: "RDD"
Output: "Dire"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator's right in the round 1.
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

Note:

1. The length of the given string will in the range [1, 10,000].

---

Dota2中有两个党派，分别是Radiant和Dire，分别用R和D表示。给定一个长度为n的字符串s，表示n个人，如果s[i]=’R’，表示第i个人是Radiant党的人；如果s[i]=’D’，表示第i个人是Dire党的人。 投票过程是从1~n不断重复的，每个人可以禁止任何一个其他人投票。如果某个人投票之后，剩下的人都是同一个党派的，则该党派胜利。问最终是哪个党派的人胜利。 使用贪心的原则，因为是round-based的投票方式，为了获胜，第i个人肯定是禁止其后的第一个非本党人员投票。比如序列DRDRR： 第一个D如果杀其后的第一个R：

1. DXDRR
2. DXDXR
3. XXDXR
4. XXDXX

Dire胜利；第一个D如果杀其后的第二个R：

1. DRDXR
2. DRXXR
3. XRXXR

Radiant胜利。 这其实很好理解，因为是round-based的投票方式，对于D来说，他必须首先把其后的第一个R杀掉，要不然很快就会轮到这个R杀己方人员了。 round-based的方式是用%n的方式实现，代码如下： [cpp] class Solution { public: string predictPartyVictory(string senate) { int r_cnt = 0, d_cnt = 0, n = senate.size(); for (int i = 0; i < n; ++i) { if (senate[i] == ‘R’) ++r_cnt; else ++d_cnt; } int pos = 0; while (r_cnt > 0 && d_cnt > 0) { if (senate[pos] == ‘X’) { pos = (pos + 1) % n; continue; } int pos_next = (pos + 1) % n; while (senate[pos_next] == senate[pos] || senate[pos_next] == ‘X’) pos_next = (pos_next + 1) % n; if (senate[pos_next] == ‘R’) –r_cnt; else –d_cnt; senate[pos_next] = ‘X’; pos = (pos + 1) % n; } return r_cnt == 0 ? "Dire" : "Radiant"; } }; [/cpp] 本代码提交AC，用时752MS。]]>