【HDU6667】Roundgod and Milk Tea【贪心】
题目大意：给你ai,bi，限制ai不能流向bi，求最大流node
题解：贪心，对于第i个班级，考虑前i-1个班级匹配完剩余多少a,b，将这些ab对第i个班级进行贪心匹配ios
匹配完若第i个班级还有剩余的ab，考虑将前面的已匹配拆分spa
考虑如何拆分code
若存在a1-b2这样一个匹配，那么能够将它拆开，并与aibi匹配成a1-bi,ai-b2，这样答案就多了1blog
因而能够想到每新贪心一个班级时，先用cnta和cntb进行贪心，若剩余ab，则在前面找已匹配进行拆分从新匹配使得答案增长it
时间复杂度o(n）io
代码：class
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define ll long long using namespace std; int T,n; struct node { ll a,b; }c[1000001]; ll ans,cnta,cntb,tc; ll ta[1000001],tb[1000001]; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld%lld",&c[i].a,&c[i].b); cnta=cntb=ans=0;int ka=1,kb=1; ll tta,ttb; for(int i=1;i<=n;i++) { //printf("%d %lld %lld\n",i,cnta,cntb); tta=c[i].a;ttb=c[i].b; if(cnta>=c[i].b)cnta-=c[i].b,ans+=c[i].b,c[i].b=0; else c[i].b-=cnta,ans+=cnta,cnta=0; if(cntb>=c[i].a)cntb-=c[i].a,ans+=c[i].a,c[i].a=0; else c[i].a-=cntb,ans+=cntb,cntb=0; tc=min(c[i].a,c[i].b); while(tc && ka<i) { if(ta[ka]>=tc)ans+=tc,c[i].a-=tc,c[i].b-=tc,ta[ka]-=tc,tc=0; else ans+=ta[ka],c[i].a-=ta[ka],c[i].b-=ta[ka],tc-=ta[ka],ka++; } while(tc && kb<i) { if(tb[kb]>=tc)ans+=tc,c[i].a-=tc,c[i].b-=tc,tb[kb]-=tc,tc=0; else ans+=tb[kb],c[i].a-=tb[kb],c[i].b-=tb[kb],tc-=tb[kb],kb++; } ta[i]=tta-c[i].a;tb[i]=ttb-c[i].b; cnta+=c[i].a;cntb+=c[i].b; //printf("%d %lld %lld %lld\n",i,cnta,cntb,ans); } //printf("%lld %lld %lld\n",cnta,cntb,ans); printf("%lld\n",ans); } return 0; }
心得：对贪心还不太会，还要继续努力stream