CF1914E2

题意

Alice和Bob分别有一些石头，石头一共有 \(n\) 种不同颜色，Alice有 \(a_i\) 个第 \(i\) 种石头，Bob有 \(b_i\) 个第 \(i\) 种石头。

每回合(Alice先手)可以选择一种颜色石头，丢弃自己的一个石头，并让对方丢弃所有这种颜色的石头。当两人手中没有相同颜色石头时，游戏结束。

对于一场游戏，分数为Alice手中石头与Bob石头的差值，记为 \(A-B\)。Alice希望分数最大化，Bob希望分数最小化，问最终得分。

思路

对于两个人来说，他们都希望每回合可以选择对方数量尽可能多的石头丢掉，并且自己的这种石头数量也尽可能大。这样既可以保护自己的这种石头不被对方丢掉，又能最大限度地削减对方石头。也就是说，两人希望先选择 \(a_i+b_i\) 最大的石头。

具体来说，对于先手的一方，假设有 \(i\) 和 \(j\) 颜色石子，满足 \(a_i+b_i\geq a_j+b_j\)，如果先手方先选择 \(j\) 颜色石子，后手方选择 \(i\) 颜色石子是更优的策略，那么最终对得分贡献为 \((a_j-1+0)-(b_i-1+0)=a_j-b_i\)。而先手方选择 \(i\) 颜色石子的贡献为 \(a_i-b_j\)。由假设可知，\(a_i-b_j\geq a_j-b_i\)，也就是说，这种策略不是最好的策略。

所以，对于先手方(Alice)，一定先选 \(a_i+b_i\) 最大的一种石子。 对于后手方(Bob)，在一个回合后变为先手方，因此采取同样策略。

至此，我们已经知道，只要将每种石头按照 \(a_i+b_i\) 从大到小排序，依次选择计算得分，得到的结果就是我们想要的答案。

记得开 long long 。

Code

#include<iostream>
#include<algorithm>
#define int long long 
using namespace std;
const int N=2e5+10;
struct node{
    int a,b,c;
}q[N];
int T,n;
bool cmp(node x,node y){
    return x.c>y.c;
}
signed main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        for(int i=1;i<=n;++i) scanf("%lld",&q[i].a);
        for(int i=1;i<=n;++i) scanf("%lld",&q[i].b),q[i].c=q[i].b+q[i].a;
        sort(q+1,q+n+1,cmp);
        int sum=0;
        for(int i=1;i<=n;++i){
            if(i&1){
                sum+=q[i].a-1;
            }else{
                sum-=q[i].b-1;
            }
        }
        printf("%lld\n",sum);
    }
    return 0;
}