AT2672 Coins

传送门

按理说想到转化问题之后就不难了吧，可是我还是不会写

一个很容易想到的转化就是差分，将银币数和铜币数都减去金币数，这样就转化为\(x+y+z\)个钱币选\(y\)个银币和\(z\)个铜币的最大数量了

然后我这个菜逼就不会做了

设总钱币数为\(n\)，银币\(x[i]\)个，铜币\(y[i]\)个，就可以按\(x[i]-y[i]\)排序

然后很显然的就是一定是前\(k\)个选银币，后\(n-k\)个选铜币（显而易见的贪心）

枚举\(k\)，用一个堆来维护就好了

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<queue>

using namespace std;

void read(int &x){

    char ch;bool ok;

    for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;

    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;

}

#define rg register

const int maxn=1e5+10;

int x,y,z,n;long long ans,sum[maxn],num;

struct oo{int x,y;}a[maxn];

bool cmp(oo a,oo b){return a.x-a.y<b.x-b.y;}

priority_queue<int,vector<int>,greater<int> >q;

int main(){

	read(x),read(y),read(z),n=x+y+z;

	for(rg int i=1,u,v,w;i<=n;i++){

		read(u),read(v),read(w);

		num+=u,v-=u,w-=u;

		a[i].x=v,a[i].y=w;

	}

	sort(a+1,a+n+1,cmp);long long now=0;

	for(rg int i=1;i<=z;i++)now+=a[i].y,q.push(a[i].y);

	for(rg int i=z+1;i<=n;i++){

		sum[i-1]=now,q.push(a[i].y);

		now+=a[i].y,now-=q.top();q.pop();

	}

	sum[n]=now;

    while(!q.empty())q.pop();now=0;

	for(rg int i=n;i>=n-y+1;i--)now+=a[i].x,q.push(a[i].x);

	for(rg int i=n-y;i>=z;i--){

	    ans=max(ans,now+sum[i]+num),q.push(a[i].x);

		now+=a[i].x,now-=q.top();q.pop();

	}

    printf("%lld\n",ans);

}

巴特西

AT2672 Coins

传送门

最新文章

热门文章