题目描述

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(夜魇)

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

禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。

宣布胜利： 如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 Radiant 或 Dire。

算法1

(贪心) $O(n)$

题解1：这题贪心的思路很简单，就是轮到每个还有用权利的人行使权力的时候，那么他肯定是尽量去禁止最近的当前轮还没有表决的对方选手禁止他在当前轮和未来的权利，如果没有这样的话，那么就从已经行使过权利的对方选手选择一个人禁止他在剩下轮的权力，如果还没有的话，那么说明已经没有敌方选手了，直接获胜。直接模拟的话代码就会比较丑陋，但是很容易理解：这里我们使用字符O代表当前选手被out禁止权利。

    string predictPartyVictory(string senate) {
        int n = senate.size();
        while(true)
        {
            for(int i = 0 ; i < n ; i ++)
            {
                int k = i + 1;
                if(senate[i] == 'R')
                {
                    while(k < n && (senate[k] == 'R' || senate[k] == 'O'))
                        k ++;
                    if(k < n) senate[k] = 'O';
                    else 
                    {
                        k = 0;
                        while(k < i && (senate[k] == 'R' || senate[k] == 'O'))
                            k ++;
                        if(k < i) senate[k] = 'O';
                        else return "Radiant";
                    }
                }else if(senate[i] == 'D')
                {
                    while(k < n && (senate[k] == 'D' || senate[k] == 'O'))
                        k ++;
                    if(k < n) senate[k] = 'O';
                    else 
                    {
                        k = 0;
                        while(k < i && (senate[k] == 'D' || senate[k] == 'O'))
                            k ++;
                        if(k < i) senate[k] = 'O';
                        else return "Dire";
                    }
                }
            }
        }
        return "";
    }

算法2

(贪心) $O(n)$

题解2：延续上述的贪心思路，但是代码实现上更加简洁，运行时间也直接从200ms变成了8ms：我们使用两个布尔变量，标记当前轮是否遇到过R或者D，cnt代表当前轮当目前为止有投票权利的人中R比D多的人数。

如果当时当前人为R，如果cnt < 0，说明前面D的人更多，说明当前这个人肯定在之前的投票中被禁止权利了，那么我么把这个标记为O。

如果当时当前人为D，如果cnt < 0，说明前面R的人更多，说明当前这个人肯定在之前的投票中被禁止权利了，那么我么把这个标记为O。

    string predictPartyVictory(string senate) {
        int n = senate.length(),cnt = 0;
        bool flag_r = true,flag_d = true;
        while(flag_r && flag_d)
        {
            flag_r =false,flag_d = false;
            for(int i = 0 ; i < n ; i ++)
            {
                if(senate[i] == 'R')
                {
                    if(cnt < 0) senate[i] = 'O';
                    cnt ++;
                    flag_r = true;
                }else if(senate[i] == 'D')
                {
                    if(cnt > 0) senate[i] = 'O';
                    cnt --;
                    flag_d = true;
                }
            }
        }
        return flag_r ? "Radiant" : "Dire";
    }