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;
}