本文主要是介绍题解: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];
}
顾得拜!
这篇关于题解:CF1914E-Game with Marbles的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!