99: AGC-018C 堆+思维

$des$
有 $X + Y + Z$ 个人，第 $i$ 个人有 $A_i$ 个金币，$B_i$ 个银币，$C_i$ 个铜币。
选出 $X$ 个人获得其金币，选出 $Y$ 个人获得其银币，选出 $Z$ 个人获得
其铜币，在不重复选某个人的前提下，最大化获得的币的总数。
$sol$
令 $A_i = A_i - C_i, B_i = B_i - C_i$ ，问题变为选出 $X$ 个人获得
其金币，选出 $Y$ 个人获得其银币，再将答案加上 $\sum C_i$.
按 $A_i$ 从大到小排序，枚举选出的 $X$ 个人中 $A_i$ 最小的人，显然这个
人之前的人要么在选出的 $X$ 个人中，要么在选出的 $Y$ 个人中。
因为假设存在 $j \in [1, i]$ 并没有使用 $j$, 那么把 $A_i$ 换成 $A_j$ 答案一定更优
那么只要对每个位置 $i, i \in [X, X + y]$ 计算两个信息：
$i$ 之前 $A_i - B_i$ 最大的 $X$ 个人的 $A_i - B_i$ 的和，这里相当于令所有的 $A_i = A_i - B_i$
最后再加上 $\sum B_i$.
$i$ 之后 $B_i$ 最小的 $Z$ 个人的 $B_i$ 之和, 这 $Z$ 个人是选 $C$ 的。
于是我需要从前往后扫一遍，用小根堆维护当前 $A_i - B_i$ 最大的 $X$ 个人，每加入一个人与堆顶比较；
再从后往前用大根堆维护第二个信息即可。
时间复杂度 $O(nlogn)$

$code$

#include <bits/stdc++.h>

#define LL long long

using namespace std;

#define gc getchar()

inline LL read() {

    LL x = ; char c = gc;

    while(c < '' || c > '') c = gc;

    while(c >= '' && c <= '') x = x *  + c - '', c = gc;

    return x;

}

#define Rep(i, a, b) for(int i = a; i <= b; i ++) 

const int N = 1e5 + ;

struct Node {

    LL A, B, C, A_B;

} Num[N];

LL L[N], R[N];

priority_queue <LL, vector<LL>, greater<LL> > Q;

priority_queue <LL, vector<LL>, less<LL> > Qu;

bool Cmp(Node a, Node b) {

    return a.A > b.A;

}

int main() {

    LL X, Y, Z, n;

    LL Sum_C = , Sum_B = , Sum = ;

    X = read(), Y = read(), Z = read();

    n = X + Y + Z;

    Rep(i, , n) {

        Num[i] = (Node) {read(), read(), read(), };

        Sum_C += Num[i].C;

        Num[i].A -= Num[i].C, Num[i].B -= Num[i].C;

        Num[i].A_B = Num[i].A - Num[i].B;

        Sum_B += Num[i].B;

    }

    sort(Num + , Num + n + , Cmp);

    Rep(i, , X) Q.push(Num[i].A_B), Sum += Num[i].A_B;

    L[X] = Sum;

    Rep(i, X + , X + Y) {

        int a_b = Num[i].A_B, tp = Q.top();

        if(a_b > tp) {

            Q.pop(); Q.push(a_b); Sum += a_b - tp;

        }

        L[i] = Sum;

    }

    Sum = ;

    for(int i = n; i > X + Y; i --) Qu.push(Num[i].B), Sum += Num[i].B;

    R[X + Y + ] = Sum;

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

        int b = Num[i].B, tp = Qu.top();

        if(b < tp) {

            Qu.pop(); Qu.push(b); Sum += b - tp;

        }

        R[i] = Sum;

    }

    LL Answer = - 1e18;

    Rep(i, X, X + Y) {

        Answer = max(Answer, L[i] - R[i + ]);

    }

    cout << Answer + Sum_C + Sum_B;

    return ;

}

巴特西

99: AGC-018C 堆+思维

最新文章

热门文章