有三个背包,三个背包里分别有 A B C 个数字,每次操作可以从任意一个背包中挑选一个数字 x,然后在另外两个背包中挑选一个数字 y 将其变为 y-x,这样操作直至三格背包中剩下一个数字为止,求最后的结果最大是多少
将 A 分为 <a,A'> B分为 <b,B'>,C分为 <c,C'>,其中 a,b,c 为背包中的任意元素,A‘ 为除 a 之外的 A 中的所有元素
很容易发现对某个数进行操作偶数次那么他的贡献是正的,操作奇数次贡献是负的,
对于 A 来说,必须要把 A’ 消掉,所以将 A' 移出,其余两个二元组变为 <b-A',B'>,<c,C'>
- 要保证这两个二元组对 a 的贡献尽可能的大,使得 B' C' 为正的加进去,所以 <b-A'-C'>,<c-B'>,这样最后的 a=a-b+A'+C'-c+B',保证 a 最大,那么 b,c 最小
- 如果不保证 B‘,C' 都是正数的话 ,那么他们将变为 <b-A'-c,B'-C'> ,最终 a=a-b+A'+c-B'+C',也就是说减去完整的 B
const int N=3e5+5;
int i,j,k;
int n,m;
ll a[N];
int main()
{
//IOS;
int x,y,z;
while(~sddd(x,y,z)){
ll sum[4]={0};
for(int i=1;i<=x;i++) sd(a[i]),sum[1]+=a[i];
for(int i=1;i<=y;i++) sd(a[i+x]),sum[2]+=a[i+x];
for(int i=1;i<=z;i++) sd(a[i+x+y]),sum[3]+=a[i+x+y];
sort(a+1,a+1+x);
sort(a+1+x,a+1+x+y);
sort(a+1+x+y,a+1+x+y+z);
ll ans=sum[1]+sum[2]+sum[3];
ll res=max(ans-2*(a[1]+a[x+1]) , max(ans-2*(a[1]+a[x+y+1]),ans-2*(a[x+1]+a[x+y+1])));
res=max(max(res,ans-2*sum[1]) , max(ans-2*sum[2],ans-2*sum[3]));
pll(res);
}
//PAUSE;
return 0;
}