Codeforces #693 D: Even-Odd Game

题目链接

题目大意

$n$个数,Alice和Bob轮流取一个,Alice得分为所有她取的数中偶数的和,Bob得分为他所有取得数中奇数的和。Alice先手,取到没有数字时结束,得分高者胜。若两人均采取最优策略,试问输赢。

个人思路

Alice取现有最大偶数,Bob取现有最大奇数。但是这样连Sample Case 1都过不去。

不妨看Sample Case 2:

3
3 2 1

/*按照最开始的思路是Bob胜,但若Alice先取3是可以做到平局的*/
//直接看Alice取了3之后的情况: 2 1
//显然此时Bob的最优策略是取2打平,而不是去取最大的奇数1

这说明只盯着最大的能给自己加分的数拿是行不通的,既然这样,那我们可以尝试着修改一下条件。

显然我们去拿小的数不合算,那我们是不是可以去拿能给对方加分的数呢?

正解

从Simple Case 2的情况中我们可以看出有时候我们需要拿一个数,尽管这个数不能给自己加分,但是因为你拿了别人就拿不到,进而对自己有利,当然,凭借着你最朴素的情感判断一下,我们优先选大的。

因为两人都只直接拿最大的,所以直接排序后遍历统计得分即可。

证明

对于所剩的最大的两个数:最大的记为x,次大的记为y。现在对于Alice而言:

  • x为偶数、y为奇数:直接选x
  • x、y奇偶性相同:选择较大的x让自己加更多分或者让对方加不到更多分
  • x为奇数且y为偶数:若Alice选择y加分,则Bob可选x加更多的分,但若Alice选择x不加分,则Bob选y也加不到分。

三种情况都是选大的更优,对于Bob的证明方法也相同。

Code

#include<bits/stdc++.h>
using namespace std;
int T,n,num[200002];
long long cnta,cntb;
int main(){
	for(scanf("%d",&T);T--;cnta=cntb=0){
		scanf("%d",&n);
		for(int i(1);i<=n;++i)
			scanf("%d",&num[i]);
		sort(num+1,num+1+n);
		bool who=1;
		for(int i(n);i>=1;--i){
			if(who)
				cnta+=(num[i]&1)?0:num[i];
			else cntb+=(num[i]&1)?num[i]:0;
			who=!who;
		}
		printf((cnta==cntb)?"Tie\n":(cnta>cntb)?"Alice\n":"Bob\n");
	}
}
暂无评论

发送评论 编辑评论


上一篇
下一篇