首页 > 代码库 > 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 玩具(三分+贪心)