题解：CF1467C Three Bags

pbcoding · 2026-07-24 10:32:16 · 题解

题目大意

给出 3 个多重集，每次可以选取两个不同集合里的两个数字，把一个数减到另一个数上。如果最后只剩下一个数字，那么最大是多少？

分析过程

很明显，从样例中就可以看出，要凑负数，因为负负得正，最终减去一个负数时就会变大。

而想要凑出最小的负数，就必须拿最小的数减去尽可能大的数字，但是并不是所有的数字都能被最小数减去。

和最小数字同集合内的数字必须由其他集合中的数字减去，而这个数字也要尽可能小，这不仅会使得当前数更小，也使得最小数减去的数更大。

先假设集合按最小值从小到大排序，设 min_i 为集合 i(1\le i\le3) 中的最小数字，sum_i 为集合 i 中除了最小值以外的和，则存在以下两种情况：

最终两者取最大值即可。

记得开 long long。

代码

#include<iostream>
#include<algorithm>
#define sqrt(x) __builtin_sqrt(x)
#define memcpy(dest, src, n) __builtin_memcpy(dest, src, n)
#define memset(st, val, n) __builtin_memset(st, val, n)
#define memmove(dest, src, n) __builtin_memmove(dest, src, n)
#define closeios() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fropen(x) freopen(x".in", "r", stdin);freopen(x".out", "w", stdout)
#define ep emplace
#define eb emplace_back
#define pii pair<int, int>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
template<typename t> t sqr(t x){return (x*x);}
template<typename t> t abs(t x){return (x>0?x:-x);}
template<typename t> t inrange(t n, t l, t r){return (l<=n&&n<=r);}
#ifdef ONLINE_JUDGE
const bool use_stderr=0;
#else
const bool use_stderr=1;
#endif
template<typename... args>
void errorf(const char* format, args... v){if(use_stderr)fprintf(stderr, format, v...);}
int       log2(int x){return (31-__builtin_clz(x));}
long long log2(long long x){return (63-__builtin_clzll(x));}
#define int2ll 1
#if int2ll
#define intEx signed
#define int long long
#else
#define intEx int
#define ll long long
#endif
using namespace std;

const int maxn=300005, inf=998244353;
int n1, n2, n3, a[4][maxn], min1=inf, min2=inf, min3=inf, sum1, sum2, sum3, sum, ans;

intEx main(){
//  fropen("");
    // code
    cin >> n1 >> n2 >> n3;
    for(int i=1;i<=n1;i++){
        cin >> a[1][i];
        min1 = min(min1, a[1][i]); // 统计最小值
        sum1 += a[1][i]; // 统计总和
    }
    for(int i=1;i<=n2;i++){
        cin >> a[2][i];
        min2 = min(min2, a[2][i]);
        sum2 += a[2][i];
    }
    for(int i=1;i<=n3;i++){
        cin >> a[3][i];
        min3 = min(min3, a[3][i]);
        sum3 += a[3][i];
    }
    sum1 -= min1; // 除最小值以外
    sum2 -= min2;
    sum3 -= min3;
    sum = sum1+sum2+sum3;
    ans = max(ans, min1-min2-min3+sum); // 第一种情况
    ans = max(ans, min2-min1-min3+sum);
    ans = max(ans, min3-min1-min2+sum);
    ans = max(ans, min2-min1+min3-sum1+sum2+sum3); // 第二种情况
    ans = max(ans, min3-min1+min2-sum1+sum2+sum3);
    ans = max(ans, min1-min2+min3+sum1-sum2+sum3);
    ans = max(ans, min3-min2+min1+sum1-sum2+sum3);
    ans = max(ans, min1+min2-min3+sum1+sum2-sum3);
    ans = max(ans, min2+min1-min3+sum1+sum2-sum3);
    // 也可以用结构体把 min 和 sum 放在一起排序再计算
    cout << ans;
    return 0;
}