[CF1467C] Three Bags - 思维

[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;
}
上一篇:Three.js - dat.GUI库的使用详解


下一篇:K - Three swimmers