NKOJ 1533 玩具（三分+贪心+单调队列）

发表于 |
字数统计: 1,158字 | 阅读时长 ≈ 5min

P1533【Usaco Nov08 Gold】玩具

问题描述

Bessie的生日快到了, 她希望用D (1 <= D <= 100,000; 70%的测试数据都满足1 <= D <= 500)天来庆祝. 奶牛们的注意力不会太集中, 因此Bessie想通过提供玩具的方式来使它们高兴. 她已经计算出了第i天需要的玩具数T_i (1 <= T_i <= 50). Bessie的幼儿园提供了许多服务给它们的奶牛程序员们, 包括一个每天以Tc (1 <= Tc <= 60)美元卖出商品的玩具店. Bessie想尽可能的节省钱, 但是Farmer John担心没有经过消毒的玩具会带来传染病(玩具店卖出的玩具是经过消毒的).

有两种消毒的方式. 第1种方式需要收费C1美元, 需要N1个晚上的时间; 第2种方式需要收费C2美元, 需要N2个晚上的时间(1 <= N1 <= D; 1 <= N2 <= D; 1 <= C1 <= 60;1 <= C2 <= 60). Bessie在party结束之后把她的玩具带去消毒. 如果消毒只需要一天,那么第二天就可以拿到; 如果还需要一天, 那么第三天才可以拿到.

作为一个受过教育的奶牛, Bessie已经了解到节约的意义. 帮助她找到提供玩具的最便宜的方法.

输入格式

  • 第 1 行: 六个用空格隔开的整数 D, N1, N2, C1, C2, Tc
  • 第 2..D+1 行: 第 i+1 行包含一个整数: T_i

输出格式

  • 第 1 行: 提供玩具所需要的最小费用.

样例输入

4 1 2 2 1 3
8
2
1
6

样例输出

35

设$F(x)$表示总共买$x$个玩具提供玩具的总费用，设$G(x)$表示总共买$x$个玩具所需要的给玩具消毒的费用。

那么显然有$F(x)=G(x)+x\times Tc$
那么由于此题可以用费用流求解，那么根据VFK神犇的证明，$F(x)$的一阶导数单调不降，因此$F(x)$是下凸的单峰函数。具体证明参见VFK。

那么如何求解$G(x)$，贪心即可。
如果慢消毒的费用比快消毒高，那么显然只用快消毒。
如果买玩具比消毒便宜，那么显然全部买。
之后考虑一般情况，如果时间允许，那么显然慢消毒是更优的。
因此开三个单调队列维护，维护时间单调递减。
第一个队列$A$表示慢消毒的玩具，第二个队列$B$表示快消毒的玩具，第三个队列$C$表示还没有完成消毒的玩具。
维护时，每天用完的玩具加到C队列中。
当C队列的队首时间与现在的时间差值大于等于快消毒时间时，将他加入B中。
当B队列的队首时间与现在的时间差值大于等于慢消毒时间时，将他加入A中。
每次优先用C队列的队首，然后再用B队列的队尾，不够用就说明买的不够，返回无穷大。
贪心的正确性是显然的，具体可参考代码。

代码：

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
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<deque>
#define N 123456
using namespace std;
struct node
{
	int x,y;
	node(int a,int b){x=a;y=b;}
};
deque<node>A,B,C;
int d,n1,n2,c1,c2,tc,T[N],sum;
int ok(int k)
{
	int i,j,ans;
	A.clear();B.clear();C.clear();
	ans=(tc-c1)*k;
	A.push_back(node(k,0));
	for(i=1;i<=d;i++)
	{
		while(C.size()&&i-C.front().y>=n2)B.push_back(C.front()),C.pop_front();
		while(B.size()&&i-B.front().y>=n1)A.push_back(B.front()),B.pop_front();
		j=T[i];
		while(j)
		{
			if(A.size())
			{
				if(A.front().x>j)
				{
					A.front().x-=j;
					ans+=c1*j;j=0;
				}
				else
				{
					j-=A.front().x;
					ans+=c1*A.front().x;
					A.pop_front();
				}
			}
			else if(B.size())
			{
				if(B.back().x>j)
				{
					B.back().x-=j;
					ans+=c2*j;j=0;
				}
				else
				{
					j-=B.back().x;
					ans+=c2*B.back().x;
					B.pop_back();
				}
			}
			else return 1e9;
		}
		C.push_back(node(T[i],i));
	}
	return ans;
}
void EF(int l,int r)
{
	int lmid,rmid,ans=1e9;
	while(l+2<r)
	{
		lmid=(r-l)/3+l;
		rmid=(lmid+r)/2;
		if(ok(lmid)>ok(rmid))l=lmid;
		else r=rmid;
	}
	while(l<=r)ans=min(ans,ok(l)),l++;
	printf("%d",ans);
}
int main()
{
	int i;
	scanf("%d%d%d%d%d%d",&d,&n1,&n2,&c1,&c2,&tc);
	for(i=1;i<=d;i++)scanf("%d",&T[i]),sum+=T[i];
	if(tc<=c1&&tc<=c2){printf("%d",sum*tc);return 0;}
	if(n1<n2)swap(n1,n2),swap(c1,c2);
	if(c1>=c2)n1=n2,c1=c2;
	EF(0,sum);
}