题解：CF1914E-Game with Marbles

题解：CF1914E-Game with Marbles

事先说明一下，本题解不讲解简单数据范围的算法，因为复杂数据范围的就很简单。

这道题的大体意思是这样的：小A有颜色为i(i=1~n)的小球a[i]个，小B有颜色为i(i=1~n)的小球b[i]个。现在他们进行一次比赛，规则如下：由双方轮流操作，小A先来，每次操作，操作方将选择一个颜色x(x=1~n)，并保证双方此时都至少有一个该颜色的球，之后自己吃掉自己的一个颜色为x的球，并让对方吃掉对方所有的颜色为x的球，之后让下一个人操作，直到不存在任何一个x(x=1~n)使得双方都至少有一个颜色为x的球。该游戏结束后，得分是小A还没吃的球的个数减去小B还没吃的球的个数。小A想让分数越高越好，小B反之，假设他们的智商都很高，都能是每一步都达到最优效果。

其实我不知道为什么要设置E1，因为没有意义呀，E2就很可做了。当然感兴趣的朋友们可以尝逝去做一下，建议直接提交E2的代码。

因此，我们只需要按照a[i]+b[i]对i进行升序排序，小A从后往前取n、n-2、n-4、……，小B取剩下的，即n-1、n-3、n-5、……，就相当于双方轮流取目前最优的。

好了，终于到了大家喜闻乐见的代码（Ctrl+C、Ctrl+V）环节了，AC code走起！

#include<bits/stdc++.h>
#define?int?long?long
#define?N?220000
using?namespace?std;
int?a[N]={},b[N]={},c[N]={},n=0,t=0;
bool?cmp(int?x,int?y);
signed?main(){
????scanf("%lld",&t);
????while(t--){
????????scanf("%lld",&n);
????????for(int?i=1;i<=n;i++){
????????????scanf("%lld",&a[i]);
????????}
????????for(int?i=1;i<=n;i++){
????????????scanf("%lld",&b[i]);
????????}
????????int?ans=0;
????????for(int?i=1;i<=n;i++){
????????????ans+=a[i]-b[i];
????????????c[i]=i;
????????}
????????sort(c+1,c+1+n,cmp);
????????for(int?i=n;i>=1;i-=2){
????????????ans+=b[c[i]]-1;
????????}
????????for(int?i=n-1;i>=1;i-=2){
????????????ans-=a[c[i]]-1;
????????}
????????printf("%lld\n",ans);
????}
????return?0;
}
bool?cmp(int?x,int?y){
????return?a[x]+b[x]<a[y]+b[y];
}

顾得拜！