AGC018C Coins

概述atcoder (老版atcoder和新版的访问速度不是一个级别的（划掉) 这个题一个很关键的点：只考虑\(x,y\),不考虑\(z\) 我们假设\(i\)选择\(A_i\),\(j\)选择\(B_j\)比两者交换选择时更优,则有\(A_i+B_j>A_j+B_i\),移项得\(A_i-B_i>A_j-B_j\).做到这里一个显然的贪心就出来了：我们将所有的人按照\(A_i-B_i\)从大到小排序

atcoder
(老版atcoder和新版的访问速度不是一个级别的（划掉)

这个题一个很关键的点：只考虑\(x,y\),不考虑\(z\)

我们假设\(i\)选择\(A_i\),\(j\)选择\(B_j\)比两者交换选择时更优,则有\(A_i+B_j>A_j+B_i\),移项得\(A_i-B_i>A_j-B_j\).做到这里一个显然的贪心就出来了：我们将所有的人按照\(A_i-B_i\)从大到小排序,前\(x\)个人选择\(A_i\),剩下的\(y\)个人选择\(B_i\)即为最优决策

那么现在再来考虑\(z\)的情况,首先继续按照\(A_i-B_i\)排序,那么同样不会存在排在前面的选择\(B_i\)同时排在后面的选择了\(A_i\)的情况,因此必然存在一个分界点使得分界点之前的一段不会出现\(B_i\),分界点之后的一段不会出现\(A_i\).再考虑\(C_i\)就会发现这两段分别是与最开始相同的问题,我们对每个子问题开一个堆,同时在枚举分界点的过程中维护当前所选择的\(A_i\)或者是\(B_i\)即可,具体过程可以参照下面的代码

#include<iostream>#include<string.h>#include<string>#include<stdio.h>#include<algorithm>#include<vector>#include<math.h>#include<queue>#include<set>#include<map>using namespace std;typedef long long ll;typedef long double db;typedef pair<int,int> pii;const int N=10000;const db pi=acos(-1.0);#define lowbit(x) (x)&(-x)#define sqr(x) (x)*(x)#define rep(i,a,b) for (register int i=a;i<=b;i++)#define per(i,b) for (register int i=a;i>=b;i--)#define fir first#define sec second#define mp(a,b) make_pair(a,b)#define pb(a) push_back(a)#define maxd 998244353#define eps 1e-8struct pnode{int a,b,c;}p[300100];bool operator <(pnode p,pnode q) {return p.a-p.b>q.a-q.b;}struct node{int a,b;};bool operator <(node p,node q) {return p.a-p.b>q.a-q.b;}priority_queue<node> q;int n,na,nb,nc;ll f[300300],g[300300];int read(){    int x=0,f=1;char ch=getchar();    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}    return x*f;}int main(){    na=read();nb=read();nc=read();n=na+nb+nc;    rep(i,1,n)     {        p[i].a=read();p[i].b=read();p[i].c=read();    }    sort(p+1,p+1+n);    //rep(i,n) cout << p[i].a << " " << p[i].b << " " << p[i].c << endl;    ll sum=0;    rep(i,na)     {        node tmp;        tmp.a=p[i].a;tmp.b=p[i].c;        q.push(tmp);sum+=p[i].a;    }    f[na]=sum;    rep(i,na+1,na+nc)    {        node Now=q.top();        if (Now.a-Now.b<p[i].a-p[i].c)        {            sum-=Now.a;sum+=Now.b;            q.pop();            node tmp;            tmp.a=p[i].a;tmp.b=p[i].c;sum+=p[i].a;            q.push(tmp);        }        else sum+=p[i].c;        f[i]=sum;    }    sum=0;    while (!q.empty()) q.pop();    //rep(i,n) cout << f[i] << " ";cout << endl;    per(i,n,n-nb+1)    {        node tmp;        tmp.a=p[i].b;tmp.b=p[i].c;        q.push(tmp);sum+=p[i].b;    }    g[n-nb+1]=sum;    per(i,n-nb,na+1)    {        node Now=q.top();        //cout << Now.a << " " << Now.b << endl;        if (Now.a-Now.b<p[i].b-p[i].c)        {            sum-=Now.a;sum+=Now.b;            q.pop();            node tmp;            tmp.a=p[i].b;tmp.b=p[i].c;sum+=p[i].b;            q.push(tmp);        }        else sum+=p[i].c;        g[i]=sum;    }    ll ans=0;    //rep(i,n) cout << g[i] << " ";cout << endl;    rep(i,n-nb+1) ans=max(ans,f[i]+g[i+1]);    printf("%lld",ans);    return 0;}

总结

以上是内存溢出为你收集整理的AGC018C Coins全部内容，希望文章能够帮你解决AGC018C Coins所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。