Three Bags

发表于 分类于 ，

    这道题的意思其实就是，给你三个背包：

    每一次任选两个背包，在这两个背包中分别取出$a,b$这两个数（不放回），同时用$a-b$来替换$a$，那么经过数次操作以后，这三个背包中就只剩下一个数字了，请问这个数字的最大值。

    输入格式是：第一行分别代表了这三个背包的背包容量，之后的三行分别代表的是这三个背包的全部数字。

Three Bags

Created by LXC on Fri Jan 12 12:26:29 2024

https://codeforces.com/problemset/problem/1467/C

ranting: 1900

tag: constructive algorithms, greedy

problem

这道题的意思其实就是，给你三个背包：
每一次任选两个背包，在这两个背包中分别取出$a,b$这两个数（不放回），同时用$a-b$来替换$a$，那么经过数次操作以后，这三个背包中就只剩下一个数字了，请问这个数字的最大值。
输入格式是：第一行分别代表了这三个背包的背包容量，之后的三行分别代表的是这三个背包的全部数字。

solution

找规律

答案就两种情况。找到三个背包中各自最小值，选择其中两个最小的作为负数，其余所有值为正数，求和得到一种答案。另一种找到每个背包各自总和最小的作为负数，其余所有值为正数，求和得到另一种答案。二者取最小。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n1, n2, n3;
    cin >> n1 >> n2 >> n3;
    vector<ll> a(n1), b(n2), c(n3);
    for (auto& i:a) cin >> i;
    for (auto& i:b) cin >> i;
    for (auto& i:c) cin >> i;
    ll ma = *min_element(a.begin(), a.end()), sa = accumulate(a.begin(), a.end(), 0LL);
    ll mb = *min_element(b.begin(), b.end()), sb = accumulate(b.begin(), b.end(), 0LL);
    ll mc = *min_element(c.begin(), c.end()), sc = accumulate(c.begin(), c.end(), 0LL);
    ll ans = 0;
    ans = max(ans, sa+sb+sc-2*(ma+mb+mc-max({ma,mb,mc})));
    ans = max(ans, sa+sb+sc-2*(min({sa,sb,sc})));
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}