【题木链接】 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;
}
