【HDU6667】Roundgod and Milk Tea【贪心】

题目大意：给你ai,bi，限制ai不能流向bi，求最大流

题解：贪心，对于第i个班级，考虑前i-1个班级匹配完剩余多少a,b，将这些ab对第i个班级进行贪心匹配

匹配完若第i个班级还有剩余的ab，考虑将前面的已匹配拆分

考虑如何拆分

若存在a1-b2这样一个匹配，那么可以将它拆开，并与aibi匹配成a1-bi,ai-b2，这样答案就多了1

于是可以想到每新贪心一个班级时，先用cnta和cntb进行贪心，若剩余ab，则在前面找已匹配进行拆分重新匹配使得答案增加

时间复杂度o(n）

代码：

#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; }

心得：对贪心还不太会，还要继续努力

转载于:https://www.cnblogs.com/worcher/p/11353796.html

总结

以上是生活随笔为你收集整理的【HDU6667】Roundgod and Milk Tea【贪心】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。