「BZOJ5164」餐厅计划问题

发表于 | 分类于 | | 浏览量： 次

什么鬼，数据范围直接加上两个0？

传送门

BZOJ5164

题解

前两天刚做过这题的简化版，数据范围比较小，那题直接上网络流搞就好了。

但是这题数据范围大了好多，没法n方过百万了。

考虑一下，不难发现，总的购买餐巾的数量与购买餐巾数量一定时的最小话费呈一个单谷函数哎！

然后就可三分或者二分了查找最小值了！

但是怎么计算购买餐巾数量一定时的最小话费呢？

当然是贪心啦！

先一次性把新的餐巾都买来，有新的就用新的，没新的就尝试找一天的旧餐巾送到慢洗部，如果还是不够的话就找离当前最近的一天的旧餐巾送到快西部。

找的时候弄个并查集维护一下就好了。计算最小费用的是$O(n)$的。

注意如果不存在合法方案的话费用为$\infty$。

所以总的时间复杂度为$O(nlog\sum_{i=1}^{n}{ri})$。

然后写完之后交掉发现自己BZOJ竟然rank1。（好吧总共也没几个人A掉）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005,inf=2147483647;
int n,m1,m2,c1,c2,p,r[maxn],L=1,R,mid,lst[maxn],fa[maxn];
inline char nc()
{
	const int S=131072;static char buf[S],*L,*R;
	return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;
}
inline int read()
{
	int ret=0,f=1;char ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}
	return ret*f;
}
inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
inline int check(int cnt)
{
	int ret=cnt*p,p1=1,p2;
	memset(lst,0,sizeof(lst));
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		int ri=r[i];
		if(cnt>0)
		{
			int t=min(ri,cnt);
			ri-=t;cnt-=t;
		}
		if(ri>0)
		{
			while(p1<i&&ri>0&&i-p1>=m1)
			{
				int t=min(ri,lst[p1]);
				ri-=t;lst[p1]-=t;ret+=t*c1;
				if(lst[p1]==0) p1++;
			}
			p2=i-m2;
			while(ri>0&&p2>0&&i-p2>=m2)
			{
				int t=min(ri,lst[p2]);
				ri-=t;lst[p2]-=t;ret+=t*c2;
				if(lst[p2]==0){fa[p2]=p2-1;p2=getfa(p2-1);}
			}
			if(ri) return inf;
		}
		lst[i]=r[i];
	}
	return ret;
}
int main()
{
	n=read();m1=read();m2=read();c1=read();c2=read();p=read();
	if(c1>c2){swap(m1,m2);swap(c1,c2);}
	for(int i=1;i<=n;i++)
	{
		r[i]=read();
		R+=r[i];
	}
	while(L<=R)
	{
		mid=(L+R)>>1;
		check(mid)>=check(mid+1)?L=mid+1:R=mid-1;
	}
	printf("%d\n",check(R+1));
	return 0;
}