agc018 C C - Coins

题意

有x+y+z个人， 每个人有a[i] 个金币 b[i] 个银币， c[i]个铜币， 从n个人里面选x个人拿金， y个人拿银， z个人拿铜，所能拿到的最大金币个数是多少。

题解

首先，如果只有两种牌很好做
我们可以先固定前x个人给金
然后剩下$y$个人，他有两种情况
第一就是拿银，第二种是找之前一个金的替换
替换的肯定是$b?a$最大的一个人
这个用一个堆维护一下就可以了
然后考虑三种牌怎么做
那么就要发现一些性质，然后想办法变为两种牌的情况
我们发现，如果两个人，满足
$a_x+b_y>b_x+a_y$
那么一定是$y$拿$b$，$x$拿$a$
于是你可以发现一个性质，就是如果你按$a_x?b_x$排序的话
那么拿a的一定是在前面的，后面的一定是在后面的
这时候，如果你枚举一个中间点，前面都是a，后面都是b
那么你会发现，分成的两端都相当于是只有两种的
然后就可以按上面的方法做了
每一段的答案都可以预处理，然后$O(n)$合并就可以了
CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const LL N=100005;
LL x,y,z,n;
LL ans=0;
struct qq
{
    LL a,b,c;
}s[N];
bool cmp1 (qq x,qq y)	{
    return x.a-x.b>y.a-y.b;}
LL l[N],r[N];
priority_queue<LL> q;
int main()
{
    scanf("%lld%lld%lld",&x,&y,&z);n=x+y+z;for (LL u=1;u<=x+y+z;u++)	scanf("%lld%lld%lld",&s[u].a,&s[u].b,&s[u].c);sort(s+1,s+1+n,cmp1);/*printf("\n");for (LL u=1;u<=n;u++) printf("%lld %lld %lld\n",s[u].a,s[u].b,s[u].c);printf("\n");*/LL sum=0;for (LL u=1;u<=x;u++) {
    sum=sum+s[u].a;q.push(s[u].c-s[u].a);}l[x]=sum;for (LL u=x+1;u<=x+z;u++){
    //这个点选c s[u].c;//这个点选a top+s[u].aLL x=q.top();if (x+s[u].a<s[u].c)//用后面这种 sum=sum+s[u].c;else{
    sum=sum+x+s[u].a;q.pop();q.push(s[u].c-s[u].a);}l[u]=sum;}
// for (LL u=x;u<=x+z;u++) printf("%lld\n",l[u]);while (!q.empty()) q.pop();sum=0;for (LL u=n;u>n-y;u--){
    sum=sum+s[u].b;q.push(s[u].c-s[u].b);}r[n-y+1]=sum;for (LL u=n-y;u>x;u--){
    LL x=q.top();if (x+s[u].b<s[u].c)sum=sum+s[u].c;else{
    sum=sum+x+s[u].b;q.pop();q.push(s[u].c-s[u].b);}r[u]=sum;}/*for (LL u=x+1;u<=n;u++) printf("%lld ",r[u]);printf("\n");*/for (LL u=x;u<=x+z;u++)	ans=max(ans,l[u]+r[u+1]);printf("%lld\n",ans);return 0;
}