AT_agc018_c [AGC018C] Coins 题解

题意：

有 \(x+y+z\) 个人，第 \(i\) 个人有 \(A_i\) 个金币，\(B_i\) 个银币，\(C_i\) 个铜币。

要选出 \(x\) 个人获得其金币，选出 \(y\) 个人获得其银币，选出 \(z\) 个人获得其铜币。在不重复选某个人的情况下，最大化获得的币的总数。

数据范围：

\(1\le x+y+z\le 10 ^ 5,1 \le A_i,B_i,C_i \le 10^9\) 。

做法和 P5470 [NOI2019] 序列类似，经典套路了。

我们可以先凑满 \(x,y,z\) 人，然后开始反悔贪心。

将一个 \(x\) 放到 \(y\) 去，再从 \(y\) 中拿一个到 \(x\) 。
将一个 \(x\) 放到 \(z\) 去，再从 \(z\) 中拿一个到 \(x\) 。
将一个 \(y\) 放到 \(z\) 去，再从 \(z\) 中拿一个到 \(y\) 。
将一个 \(x\) 放到 \(y\) 去，再从 \(y\) 中拿一个到 \(z\) ，最后从 \(z\) 中拿一个到 \(x\) 。
将一个 \(x\) 放到 \(z\) 去，再从 \(z\) 中拿一个到 \(y\) ，最后从 \(y\) 中拿一个到 \(x\) 。

那么我们维护所有转移产生的贡献即可，也就是弄 \(6\) 个堆。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码详见参考文献1，实现类似 P5470 ，太复杂了，这里暂时就直接贴他写的代码了。

// P5470
#include <bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define fr first
#define sd second
#define pa pair<ll, ll>
#define FOR(i, a, b) for (ll i = a; i <= b; i++)
#define REP(i, a, b) for (ll i = a; i >= b; i--)
#define MEM(a) memset(a, 0, sizeof(a))
#define N 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline ll read()
{
    char ch = getchar();
    ll s = 0, w = 1;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}
inline ll lowbit(ll x) { return x & (-x); }
ll n, X, Y, Z;
ll a[N], b[N], c[N];
ll vis[N], ans;
priority_queue<pa, vector<pa>, less<pa>> q1, q2, q3, q4, q5, q6;
inline void add(ll x)
{
    q1.push(mp(b[x] - a[x], x)); // x->y
    q2.push(mp(c[x] - b[x], x)); // y->z
    q3.push(mp(a[x] - c[x], x)); // z->x

    q4.push(mp(c[x] - a[x], x)); // x->z
    q5.push(mp(b[x] - c[x], x)); // z->y
    q6.push(mp(a[x] - b[x], x)); // y->x
}
int main()
{
    // ios::sync_with_stdio(false);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    X = read(), Y = read(), Z = read();
    n = X + Y + Z;
    FOR(i, 1, n)
    a[i] = read(),
    b[i] = read(), c[i] = read();
    FOR(i, 1, X)
    vis[i] = 1,
    ans += a[i];
    FOR(i, X + 1, X + Y)
    vis[i] = 2,
    ans += b[i];
    FOR(i, X + Y + 1, X + Y + Z)
    vis[i] = 3,
    ans += c[i];
    FOR(i, 1, n)
    add(i);
    while (true)
    {
        while (!q1.empty() && vis[q1.top().sd] != 1)
            q1.pop();
        while (!q2.empty() && vis[q2.top().sd] != 2)
            q2.pop();
        while (!q3.empty() && vis[q3.top().sd] != 3)
            q3.pop();

        while (!q4.empty() && vis[q4.top().sd] != 1)
            q4.pop();
        while (!q5.empty() && vis[q5.top().sd] != 3)
            q5.pop();
        while (!q6.empty() && vis[q6.top().sd] != 2)
            q6.pop(); // 反悔贪心在每次取值时弹出不合法状态往往更好写

        ll v1 = (q1.empty() ? -inf : q1.top().fr), v2 = (q2.empty() ? -inf : q2.top().fr), v3 = (q3.empty() ? -inf : q3.top().fr);
        ll v4 = (q4.empty() ? -inf : q4.top().fr), v5 = (q5.empty() ? -inf : q5.top().fr), v6 = (q6.empty() ? -inf : q6.top().fr);
        ll maxn = 0, t = 0;
        if (v1 + v2 + v3 > maxn)
            maxn = v1 + v2 + v3, t = 1; // 情况1
        if (v4 + v5 + v6 > maxn)
            maxn = v4 + v5 + v6, t = 2; // 情况2
        if (v1 + v6 > maxn)
            maxn = v1 + v6, t = 3; // 情况3
        if (v2 + v5 > maxn)
            maxn = v2 + v5, t = 4; // 情况4
        if (v3 + v4 > maxn)
            maxn = v3 + v4, t = 5; // 情况5
        if (!maxn)
            break;
        ans += maxn;
        if (t == 1)
        {
            ll x = q1.top().sd, y = q2.top().sd, z = q3.top().sd;
            vis[x] = 2, vis[y] = 3, vis[z] = 1;
            add(x);
            add(y);
            add(z);
        }
        if (t == 2)
        {
            ll x = q4.top().sd, y = q5.top().sd, z = q6.top().sd;
            vis[x] = 3;
            vis[y] = 2;
            vis[z] = 1;
            add(x);
            add(y);
            add(z);
        }
        if (t == 3)
        {
            ll x = q1.top().sd, y = q6.top().sd;
            vis[x] = 2;
            vis[y] = 1;
            add(x);
            add(y);
        }
        if (t == 4)
        {
            ll x = q2.top().sd, y = q5.top().sd;
            vis[x] = 3;
            vis[y] = 2;
            add(x);
            add(y);
        }
        if (t == 5)
        {
            ll x = q3.top().sd, y = q4.top().sd;
            vis[x] = 1;
            vis[y] = 3;
            add(x);
            add(y);
        }
    }
    cout << ans << '\n';
    return 0;
}

参考文献：

[1] https://www.luogu.com.cn/article/3wnlp2ld