AGC018C Coins (set)

题目大意：

给出n个人，每个人手里都有xi个金牌，yi个银牌，ci个铜牌。

你需要选出X个人，拿走他们手里的金牌，选出Y个人，拿走他们手里的银牌，选出Z个人，拿走他们手里的铜牌

X+Y+Z = n。并且选的这X,Y,Z个人里不能有重复的。

题解：

不妨先考虑只有金牌和银牌怎么做。

如果只有两种，就变成很简单的贪心了，依据每个人手中的金牌数x减去银牌数y然后排序，按差值选即可

现在又多了一个铜牌，我们还是按照这个思路

依据每个人手中的金牌数x减去银牌数y然后排序。

然后我们考虑如何分配我们的X和Y。

注意到，排完序以后，这里有一个奇妙的性质出现了

这个性质简单来说就是，银牌从排序靠前的元素选，金牌从排序靠后的元素选，这样做会更优

或者这样说，银牌和金牌的选择是互不交叉的。（考虑如果有交叉，那么相互交换一下会更优）

那么我们就可以这样求出答案

枚举一个k，从前k个元素中选出Y个银牌，从后n-k个元素中选出X个金牌，其他都是选铜牌

这样我们只需要把k从Y枚举到n-X就可以了

那铜牌的影响怎么处理呢？

就让金牌数和银牌数直接减去铜牌数，然后最后的答案加上铜牌数，这样所有的铜牌数就变成了0

就可以不考虑它的影响了。

对每一个k，答案就是前k个元素中最大的Y个银牌数和，加上后n-k个元素中最大的X个银牌数和

这个显然可以用set来维护。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <set>

#include <map>

#define fi first

#define se second

using namespace std;

const int maxn = 1e5 + ;

typedef pair<int, int> PII;

bool cmp(const PII &A, const PII &B){

    return A.fi - A.se < B.fi - B.se;

}

PII a[maxn];

set<int> S[];

map<int, int> H[];

int ssz[], sz[];

long long ans = , temp, ans1[maxn], ans2[maxn];

void Erase(int x, int ty){

    if(H[ty][x] == ) S[ty].erase(x);

    H[ty][x]--;

    ans -= x;

    ssz[ty]--;

}

void Insert(int x, int ty){

    if(H[ty][x] == ) S[ty].insert(x);

    H[ty][x]++;

    ans += x;

    ssz[ty]++;

}

void S_Insert(int x, int ty){

    if(ssz[ty] == sz[ty]){

        int y = *S[ty].begin();

        if(y > x) return;

        Erase(y, ty);

    }

    Insert(x, ty);

}

int main()

{

    int X, Y, Z, x, y, z;

    cin>>X>>Y>>Z;

    int n = X+Y+Z;

    for(int i = ; i <= n; i++){

        scanf("%d %d %d", &x, &y, &z);

        x -= z;

        y -= z;

        ans += z;

        a[i].fi = x;

        a[i].se = y;

    }

    temp = ans;

    ans = ;

    sort(a+, a++n, cmp);

    sz[] = Y; sz[] = X;

    for(int i = ; i <= Y; i++) S_Insert(a[i].se, );

    ans1[Y] = ans;

    for(int i = Y+; i <= n-X; i++){

        S_Insert(a[i].se, );

        ans1[i] = ans;

    }

    ans = ;

    for(int i = n; i >= n-X+; i--) S_Insert(a[i].fi, );

    ans2[n-X+] = ans;

    for(int i = n-X; i >= Y+; i--){

        S_Insert(a[i].fi, );

        ans2[i] = ans;

    }

    ans = -1e18;

    for(int i = Y; i <= n-X; i++) ans = max(ans, ans1[i]+ans2[i+]);

    cout<<ans+temp<<endl;

    return ;

}