AGC018C Coins
发布时间:2020-12-16 09:17:46 所属栏目:百科 来源:网络整理
导读:atcoder (老版atcoder和新版的访问速度不是一个级别的(划掉) 这个题一个很关键的点:只考虑 (x,y) ,不考虑 (z) 我们假设 (i) 选择 (A_i) , (j) 选择 (B_j) 比两者交换选择时更优,则有 (A_i+B_jA_j+B_i) ,移项得 (A_i-B_iA_j-B_j) .做到这里
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-8 struct 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; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |