[CF1467C] Three Bags - 思维
Description
给定 3 个集合,每个集合里有若干个数,每次可以从一个集合选择一个数 a,从另一个集合选择一个数 b,令 a=a-b,并且删除 b。操作到只剩下一个数为止。求剩下的这个数的最大值。
Solution
首先很容易想象出一个树形结构,奇数层为正,偶数层为负
有一种不错的情况是,第一层填一个数,第二层是两个来自不同集合的数,这样第三层就可以填剩下的所有数
考虑例外,如果我们只希望减去一个集合中的数,这样是可以做到的,即在第二层填上这个集合的所有数(如果不填所有,那么会掉到第四层,结果是一样的,总之不可能填在奇数层中),第三层填剩下的所有数,这样贡献为负的恰好是某一个集合内的所有数
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
vector<int> n(5);
vector<vector<int>> a(5);
for (int i = 1; i <= 3; i++)
cin >> n[i], a[i].resize(n[i] + 2);
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= n[i]; j++)
cin >> a[i][j];
for (int i = 1; i <= 3; i++)
sort(&a[i][1], &a[i][n[i] + 1]);
vector<int> mn(5), sum(5);
for (int i = 1; i <= 3; i++)
mn[i] = a[i][1];
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= n[i]; j++)
sum[i] += a[i][j];
int ans = 0;
int s = sum[1] + sum[2] + sum[3];
int ms = mn[1] + mn[2] + mn[3];
for (int i = 1; i <= 3; i++)
ans = max(ans, max(s - 2 * ms + 2 * mn[i], s - 2 * sum[i]));
cout << ans << endl;
}