E. Permutation Game

https://codeforces.com/contest/1772/problem/E

题目大意就是给一个1~n的全排序列，所有数字都是红色的，两人轮流操作，操作有三种选择，第一是将所有蓝色的数字任意排列，第二是将其中一个红色数字变蓝，第三是什么都不操作，该游戏有三种情况1胜，2胜和平局，如果最后序列为1~n的排列形式1胜，如果为n~1的排列形式则2胜利

思路:由上面我们发现，如果出现一种情况就是还剩一个就全变蓝了，则是平局，我们可以比较1~n的全排和n~1的全排和原来的序列，得到两个人赢分别需要变蓝多少个，注意这里要区分两个人都要的需要变蓝的元素

代码

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

const int N=5e5+10;

long long p[N];

int n;

int main(){

	int t;

	cin>>t;

	while(t--){

		cin>>n;

		int sum1=0,sum2=0;//统计各自需要变蓝的元素个数，不包括同时需要的

		int sum=0;//统计两个人同时需要的

		for(int i=1;i<=n;i++){

			cin>>p[i];

			if(p[i]==n-i+1&&p[i]!=i) sum1++;

			if(p[i]==i&&p[i]!=n-i+1) sum2++;

			if(p[i]!=i&&p[i]!=n-i+1) sum++;

		}

		while(sum1+sum>0||sum2+sum>0){//我们发现，如果想要赢，优先选只有自己需要的元素，再选两人都需要的元素

			if(sum1>0) sum1--;

			else sum--;

			if(sum1+sum<=0) break;

			if(sum2>0) sum2--;

			else sum--;

			if(sum2+sum<=0) break;

		}

		if(sum1+sum==0&&sum2>0) cout<<"First"<<endl;//如果第一个所需要变蓝的元素全部选完但第二个人需要的还没选完

		else if(sum2+sum==0&&sum1>0) cout<<"Second"<<endl;//第二个同上

		else cout<<"Tie"<<endl;//如果没人多余的话，说明其中最后一个是两人都需要选的，则谁先选谁就输，因此两人都会跳过形成死循环

}

}

巴特西

E. Permutation Game

最新文章

热门文章