【BZOJ1221】【HNOI2001】软件开发
【BZOJ2298】【HAOI2011】problem a

【BZOJ1229】【USACO2008 Nov】toy 玩具

Zarxdy34 posted @ 2016年2月29日 19:28 in BZOJ with tags 三分法 贪心 , 872 阅读

  这道题的原型是餐巾计划问题,来源线性规划和网络流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;
}
Avatar_small
cgh 说:
2016年9月03日 08:31

orz 不是很懂怎么证单峰


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter