首页 > 代码库 > BZOJ 1229 [USACO2008 Nov]toy 玩具（三分+贪心）
BZOJ 1229 [USACO2008 Nov]toy 玩具（三分+贪心）
【题木链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1229
【题目大意】
每天对玩具都有一定的需求ni，每天可以花f价值每条购买玩具，
当天用完的玩具可以花费fA价值每个通过快消毒在A天之后得到一条可用的，
也可以通过花费fB价值每个，通过慢消毒在B天之后获得可用的
问满足每天需求所用的最小花费。
【题解】
这是纸巾问题的费用流模型，费用流做法见 BZOJ 1221 [HNOI2001] 软件开发
但是我们发现N=100000的规模完全无法用费用流解决
我们发现在最小费用最大流的过程中，每次的最短路长度不降，
最短路是费用的差分值，所以一阶导不下降，那么费用随流量变化的函数是单峰的，
可以三分，三分之后的验证可以通过贪心来实现，
我们先假设把所有的毛巾快洗掉，到后面的天数发现之前决定快洗的毛巾放到慢洗里面也可以
那就把这个点拿出来加入到慢洗完成的队伍。
【代码】
#include <cstdio>#include <algorithm>using namespace std;const int INF=0x3f3f3f3f,N=100010;int a[N],A,B,f,fA,fB,n;struct data{int x,y;}d[N],s[N],q[N];int F(int x){ int ret=(f-fB)*x,l,r,sl,sr,ql,qr; l=sl=ql=r=1; sr=qr=0; d[l].x=-INF,d[l].y=x; for(int i=1;i<=n;i++){ while(l<=r&&i-d[l].x>=A)q[++qr]=d[l++]; while(ql<=qr&&i-q[ql].x>=B)s[++sr]=q[ql++]; int p=a[i]; while(p){ if(sl<=sr){ if(s[sr].y>p)s[sr].y-=p,ret+=p*fB,p=0; else p-=s[sr].y,ret+=s[sr--].y*fB; }else if(ql<=qr){ if(q[qr].y>p)q[qr].y-=p,ret+=p*fA,p=0; else p-=q[qr].y,ret+=q[qr--].y*fA; }else return INF; }d[++r].x=i,d[r].y=a[i]; }return ret;}int Ternary_Search(int l,int r){ while(1){ if(r-l<=5){ int fx=F(l); for(int i=l+1;i<=r;i++)fx=min(fx,F(i)); return fx; } int x=l+(r-l)/3,y=l+2*(r-l)/3; int fx=F(x),fy=F(y); if(fx!=INF&&fx<=fy)r=y; else l=x; }return 0; }int main(){ while(~scanf("%d%d%d%d%d%d",&n,&A,&B,&fA,&fB,&f)){ if(A>B)swap(A,B),swap(fA,fB); if(fA<fB)fB=fA; int l=1,r=0; for(int i=1;i<=n;i++)scanf("%d",&a[i]),r+=a[i]; printf("%d\n",Ternary_Search(l,r)); }return 0;}BZOJ 1229 [USACO2008 Nov]toy 玩具（三分+贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。