leetcode 649. Dota2 参议院

2023.9.11

        先简化一下题意：本题的意思就是每次投票中，前面的议员可以干掉后面的议员(当然是干掉敌对方的)，然后他将参与下一次的投票，而被干掉的议员则不能参与投票了。 如：[R D D] -> [R D] ->[R D]->[D] 。 最后活下来的议员则获得胜利。

         本题我是用了两个队列存储两个阵营对应的索引，索引小的议员先投票。然后每次投票完之后，将继续参与下一次投票：即在队列中再push一个索引进去，radiant.push(radiant.front() + senate.size());   然后敌对方队列pop出一个元素，代表被消灭了。 最后哪个队列不为空，哪个队列阵营就获胜了。

        代码如下：

class Solution {
public:
    string predictPartyVictory(string senate) {
        queue<int> radiant;
        queue<int> dire;
        for(int i=0; isize(); i++)
        {
            if(senate[i] == 'R') radiant.push(i);
            else dire.push(i);
        }
        while(!radiant.empty() && !dire.empty())
        {
            if(radiant.front() < dire.front())
            {
                radiant.push(radiant.front() + senate.size());//第二轮还要继续投票
            }
            else
            {
                dire.push(dire.front() + senate.size());
            }
            //一个丧失投票资格，还一个需要等到下一轮才能投票。
            radiant.pop();
            dire.pop();
        }
        if(radiant.empty()) return "Dire";
        return "Radiant";
    }
};