Three Bags CodeForces - 1467C

题意：

三堆石子，你可以取两堆石子各一个石头a,b。然后消掉a，使得b=b-a再放入b的那一堆。这样操作直到只剩下一个石子，求该石子价值最大。

题解：

构造题
可以构造出两者情况：

1. 其中两堆都是正的，一堆都是负的
2. 一个背包都是正的，另两个背包的最小值是负的，其他都是正的
   为什么是这样构造出来的呢？
   参考题解
   对于一个数如果进行奇数次操作，那么就是负贡献，偶数次操作就是正贡献
   假设最后一个数在数组a，那么a中剩下n-1个数，可以在最后先与其他数组合并，再和最后一个数合并，这样就都是正贡献。同理应用到b和c数组，就相当于b，c中只有一个数的负贡献，其他都是正，我们取b，c中最小的为负贡献
   或者我们直接选b，c中一个数组为正数组，另一个为负数组

   代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 300010;

int n1, n2, n3;
ll a[maxn], b[maxn], c[maxn];
ll s1, s2, s3;
ll m1, m2, m3;

ll ans = 0;

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
    n1 = read(), n2 = read(), n3 = read();
    for(int i = 1 ; i <= n1 ; ++i) a[i] = read(), s1 += a[i];
    for(int i = 1 ; i <= n2 ; ++i) b[i] = read(), s2 += b[i];
    for(int i = 1 ; i <= n3 ; ++i) c[i] = read(), s3 += c[i];

    ans = -1e18;

    ans = max(ans, s1 + s2 - s3); 
    ans = max(ans, s2 + s3 - s1);
    ans = max(ans, s3 + s1 - s2);

    m1 = a[1], m2 = b[1], m3 = c[1];

    for(int i = 2 ; i <= n1 ; ++i) m1 = min(m1, a[i]);
    for(int i = 2 ; i <= n2 ; ++i) m2 = min(m2, b[i]);
    for(int i = 2 ; i <= n3 ; ++i) m3 = min(m3, c[i]);

    ans = max(ans, s1 + s2 + s3 - 2 * m1 - 2 * m2);
    ans = max(ans, s1 + s2 + s3 - 2 * m1 - 2 * m3);
    ans = max(ans, s1 + s2 + s3 - 2 * m2 - 2 * m3);

    printf("%lld\n", ans);

    return 0;
}