NKOJ 1533 玩具(三分+贪心+单调队列)

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);
}