直接枚举最后剩下的数字在哪一个袋子里,这里以在 A A A为例
首先清楚一次操作消除 b b b,把 a a a替换成 a − b a-b a−b
可以理解为改变 b b b的正负号,那么对一个数进行奇数次操作是负收益,偶数次操作是正收益
那么由于 a a a中有 n 1 n_1 n1个元素,其中 n 1 − 1 n_1-1 n1−1个元素需要作为操作中的 b b b转移成负号出去
然后再作为 b b b转移回来,两次操作负负得正,所以 A A A的所有数字都是正收益
再考虑 B , C B,C B,C袋子怎么弄最优
Ⅰ. B , C B,C B,C分别剩下一个,然后分别作为 b b b给 A A A
这样 B B B除了剩下的那个数,其余数字先给 C C C,再由 C C C给 A A A,偶数次操作是正收益
C C C同理。所以只有留下来的那个数字是负收益
不难发现让 B , C B,C B,C把最小的数字留下来是最优的
Ⅱ . Ⅱ. Ⅱ.最后只有 B B B剩下了一个数,然后作为 b b b给 A A A
那么 B B B中的其余 n 2 − 1 n_2-1 n2−1个元素先转移到 C C C,然后再转移回 B B B,再一起转移回 A A A
都是奇数次操作,所以 B B B中的收益都是负收益, C C C中的收益都是正收益
这里 B B B中的其余 n 2 − 1 n_2-1 n2−1个元素先转移到 C C C,然后由 C C C直接转移给 A A A会不会更优呢?
不需要考虑,因为这么做导致:有一部分 B , C B,C B,C是正收益,一部分是负收益
然而 Ⅰ Ⅰ Ⅰ的情况一定比这样做更优
Ⅲ . Ⅲ. Ⅲ.最后只有 C C C剩下了一个数,然后作为 b b b给 A A A
和上面同理, B B B都是正收益, C C C都是负收益
然后代码就很简单了
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
#define int long long
const int inf = 1e15;
int t,n1,n2,n3,a[maxn],b[maxn],c[maxn],d[maxn];
signed main()
{
cin >> n1 >> n2 >> n3;
int sum1 = 0,sum2 = 0,sum3 = 0;
for(int i=1;i<=n1;i++) { cin >> a[i]; sum1 += a[i]; }
for(int i=1;i<=n2;i++) { cin >> b[i]; sum2 += b[i]; }
for(int i=1;i<=n3;i++) { cin >> c[i]; sum3 += c[i]; }
sort( a+1,a+1+n1 ); sort( b+1,b+1+n2 ); sort( c+1,c+1+n3 );
int ans1 = 0,ans2 = 0,ans3 = 0;
ans1 = sum1+sum2+sum3-2*(b[1]+c[1]);//分别留下一个给A
ans2 = sum1+sum2+sum3-2*(a[1]+c[1]);
ans3 = sum1+sum2+sum3-2*(a[1]+b[1]);
ans1 = max( ans1,max(sum1+sum2-sum3,sum1+sum3-sum2));//只留下一个
ans1 = max( ans1,sum2+sum3-sum1);
cout << max( ans1,max(ans2,ans3) );
}