DOJ-team-match 7-20210919小学组-取数游戏
取数游戏
首先明确一下贪心策略:
- 两人必然会从大往小取
- 当自己无法得分时,最优策略就是不让对方得分
- 当自己可以得分时,得分
所以,最后只需要便利数组,当A或B能得分时便得分,不能得分就不得分,但是不管能否得分都需要将最大的数取出
代码:
#include<bits/stdc++.h>
using namespace std;
int n,a[20010],A,B;
bool cmp(int x,int y){
return x>y;
}
int main()
int t;
cin>>t;
while(t--)
{
A=B=0;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n,cmp);
for(int i=0;i<n;i++)
{
if(i%2==0)
{
if(a[i]%2==0) A+=a[i];
}else
{
if(a[i]%2==1) B+=a[i];
}
}
if(A>B) cout<<"A";
else if(A<B) cout<<"B";
else cout<<"C";
cout<<endl;
}
return 0;
}
标签:DOJ,得分,int,取数,20210919,team,match
From: https://www.cnblogs.com/lyk2010/p/17850364.html