LeetCode--Dota2 参议院(day 2)

  今天给大家带来LeetCode中的一道算法题：参议院问题，忘记具体内容的朋友可以观看下图：

  根据题意，我们可以清楚的认识到获胜条件：那就是字符串中仅包含D或R。

  我们先以RDRDD为例进行说明：

  字符串中的第一个R行使权力，淘汰D阵营中的某一位，我们可以看见字符串中有三个D，那么该淘汰哪个呢？如果淘汰第一个D，那么字符串为RDDR（该参议员移到最后），下一个行使权力的依然是R，依然可以淘汰第一个D，字符串为DRR，此时无论如何都是R最终获得胜利。如果原字符串中第一个R先淘汰第二个D，那么字符串为DRDR，那么下一次D可以淘汰第一个R，字符串为DRD，下一次D淘汰R，D获胜。同理第三个D的分析。

  通过这个例子，我想大家应该都清楚了参议院淘汰标准：淘汰掉对方阵营最先行使权力的参议员。（参议员足够聪明）

  根据这个依据，我们直接上代码：

#include<iostream>
#include<queue>
using namespace std;
int main(){
	string str="RDRDR";
	int length=str.length();
	queue<int>q1,q2;
	for(int i=0;i<length;i++){
		if(str[i]=='R'){
			q1.push(i);//存入下标用于判断谁先行使权力 
		}
		else{
			q2.push(i);
		}
	}
	int rpull,dpull;
	while(!q1.empty()&&!q2.empty()){//当有一个队列为空时说明胜负已分 
		rpull=q1.front();
		q1.pop();
		dpull=q2.front();//拿出队首比较谁小谁先决定让对方阵营下标最小的淘汰
		q2.pop();
		if(rpull<dpull){
			q1.push(rpull+length);//淘汰掉D阵营即D无需再入队列但是R需要入队列 
			//rpull+length之所以加上length防止重新入对后对本轮产生影响让其进入下一轮 
		}
		else{
			q2.push(dpull+length);
		} 
	}
	if(q1.empty()){
		cout<<"D is win!";
	} 
	else{
		cout<<"R is win!";
	}
} 

  在下文我们给出代码解释以及需要注意的地方：

  首先给出两个队列q1，q2，用于存放D阵营和R阵营，当行使权力时，从相关阵营出队列，最后重新进入队列尾部（最后行使权力）。当某个参议员被淘汰时，将相关阵营出列即可，无需重新入队。我们需要注意一些细节：那就是重新入队时，要注意不能对当前轮次产生影响，具体看代码。

  这就是Dota2 参议院问题的全部内容，主要使用了贪心思想，淘汰掉对方阵营最先行使权力的参议员。

  多多点赞加评论，每天更新，大家一起努力！