【BZOJ1229】【USACO2008 Nov】toy 玩具

  这道题的原型是餐巾计划问题，来源线性规划和网络流24题。

  但是这题n<=100000，跑费用流显然是过不了的。

  设f(x)表示买x个玩具需要的费用，这个f(x)是个单峰函数。

  证明网上只有vfk的，然而并看不懂。大概的意思是费用流建图后，每次跑最短路，最短路的长度都是递减的，而流量就是玩具的个数，意即单位玩具的费用是随购买玩具的个数递减的。也就是说f(x)是一个单峰函数。

  然后就可以三分+贪心了。首先如果快洗店的费用比慢洗店的费用还低，那么就不需要慢洗店了，把慢洗店变成快洗店。

  这里有一个容易想到但是会WA的贪心，然而我看不懂那些题解里面关于卡这个贪心的样例到底是什么鬼...

  这个贪心的思想是每次从左往右扫，先只用玩具但不消毒，留着用。如果碰到玩具不够的情况，就找最早用完留着没处理的玩具，把它们能送慢洗店就送慢洗店，否则送快洗店，以满足当天的玩具需求。

  这个数据可以卡掉这个做法：D=4,N1=1,N2=3,C1=3,C2=1,Tc=4,T1=3,T2=1,T3=1,T4=4。

  最优方案是买4个玩具，第二天送一个去快洗店，第一天送3个去慢洗店，费用为25。

  错误的贪心则会产生26的费用，因为它会在第三天的时候发现玩具不够用，然后在第一天送一个去快洗店，这样一来第一天就只有两个未处理的玩具。把这两个玩具送去慢洗，还必须把第二天和第三天的玩具送去快洗，这样第四天才有足够的玩具，这样产生的费用就会变多。

  正确的贪心也是好想的，慢洗店的方法不变，快洗店则在慢洗无法满足要求的时候，优先选择消毒那些最晚用完留着没处理，且能够在当天之前洗完的玩具。

  一般做法两个队列就好了，我比较傻还要开个并查集维护一下...

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010,inf=~0U>>1;

int n,N1,N2,C1,C2,Tc;
int a[maxn],asum;
int ans;

int q[maxn],top1,top2;
int fa[maxn];

int Find(int x) {return (fa[x]==x)?x:fa[x]=Find(fa[x]);}

int f(int x)
{
	for (int i=1;i<=n;i++) q[i]=a[i],fa[i]=i;
	top1=1;top2=0;
	int res=Tc*x;
	for (int i=1;i<=n;i++)
	{
		top2=i-N1;
		if (x<a[i])
		{
			while (top1<=i-N2 && x<a[i])
			{
				int m=min(q[top1],a[i]-x);
				x+=m;
				q[top1]-=m;
				res+=C2*m;
				if (x<a[i]) top1++; 
			}
			while (top2>=top1 && x<a[i])
			{
				int m=min(q[top2],a[i]-x);
				x+=m;
				q[top2]-=m;
				res+=C1*m;
				if (x<a[i]) fa[top2]=Find(top2-1),top2=fa[top2];
			}
			if (x<a[i]) return inf;
		}
		x-=a[i];
	}
	return res;
}

int main()
{
	scanf("%d%d%d%d%d%d",&n,&N1,&N2,&C1,&C2,&Tc);
	if (N1>N2) swap(N1,N2),swap(C1,C2);
	if (C1<C2) C2=C1;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),asum+=a[i];
	int l=0,r=asum;
	while (r-l>2)
	{
		int m1=l+(r-l)/3,m2=l+2*((r-l)/3);
		int fm1=f(m1),fm2=f(m2);
		if (fm1!=inf && fm1<=fm2) r=m2;else l=m1;
	}
	ans=inf;
	for (int i=l;i<=r;i++) ans=min(ans,f(i));
	printf("%d\n",ans);
	return 0;
}