题解 CF1472D 【Even-Odd Game】

· · 题解

Solution：

一开始我们会简单地想到Alice一直拿偶数的最大，Bob拿奇数最大即可。

然后我们看到样例的第二组：

3
3 2 1

输出：Tie

我们并不清楚是否能拿对面的数字，即Alice拿奇数，Bob拿偶数，但是我们看到此样例时，也会去考虑这个问题。

我们可以发现，如果Alice拿了2，那么易证她必输，因此我们不难想到：如果把对面的数字拿了，Alice最多就可以拿到2，那么Alice也是可以赢的。

于是Alice拿了3。

那么如果此时Bob拿了1，那么也是易证他必输。

于是他拿了2。

结果？两人都是零，开心地爆零平局了。

那么我们可以得出，在某些时刻拿对方的数字也是不错的，即使自己啥都得不到。

然后我们思维就会想到全拿最大的数即可，但是无法证明其正确性。

那么我们尝试着这样想：Alice拿走了对方的数字，相当于对方无法拿到这个数字。我们设Alice的可以拿到的数总和为 x，Bob为 y。假设Bob本来是可以拿到这个数字 a 的，但由于Alice拿走了，导致Bob无法得到 a ，相当于 y-a （本来这个 y 中应当是包含a的），那么 x-(y-a)（做差法比较两数大小）就等于 x+a-y ，也就等于Alice拿走了 a，这样一来，Alice和Bob不再有奇偶之分。

因此，只要一直拿最大的那个数就行了。

那么代码实现也很简单：

//洛璟の代码用ans作两个数之差，若Alice得分则加上这个数，
//Bob得分减去这个数，若答案为0则为平局，大于零则Alice胜，
//反之则Bob胜，其核心思想为作差法
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int t,n;
int a[1919810];
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    return x*f;
}
bool cmp(int a,int b)
{
    return a>b;
}
signed main()
{
    t=read();
    while(t--)
    {
        int ans=0;
        n=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
        }
        sort(a+1,a+n+1,cmp);//先排序，保证他们拿的数永远是当前最大的
        for(int i=1;i<=n;i++)
        {
            if(a[i]%2==0 && i%2==1) ans+=a[i];//从大到小拿，按规则来计算加分
            else if(a[i]%2==1 && i%2==0) ans-=a[i]; //同上
        }
        if(ans>0) printf("Alice\n");//详见开头
        else if(ans==0) printf("Tie\n");
        else printf("Bob\n");
    }
    return 0;
}