BZOJ 5164: 餐厅计划问题&&1229: [USACO2008 Nov]toy 玩具（三分+贪心）

Posted On 2018年9月29日

Description

玩具 [Chen Hu, 2006] 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已经了解到节约的意义. 帮助她找到提供玩具的最便宜的方法.

Input

* 第 1 行: 六个用空格隔开的整数 D, N1, N2, C1, C2, Tc

* 第 2..D+1 行: 第 i+1 行包含一个整数: T_i

Output

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

Sample Input

4 1 2 2 1 3
8
2
1
6输入解释:
Bessie想开4天的party, 第1天需要8个玩具, 第2天需要2个玩具, 第3天需要1个玩具,
第4天需要6个玩具. 第一种方式需要$2, 用时1天; 第二种方式需要$1, 用时2天. 买
一个玩具需要$3.

Sample Output

35
输出解释:
第 1 天买8个玩具, 花去$24; 送2个玩具去快洗, 6个慢洗.
第 2 天取回2个快洗的玩具, 花去$4. 送1个玩具去慢洗.
第 3 天取回6个慢洗的玩具, 花去$6.
第 4 天取回所有的玩具(与现有的加在一起正好6个), 花去$1. 这样就用了最少的钱.

HINT

Source

Solution

第一眼网络流~~，没看数据范围还作死说了一句不是流就从楼上跳下去~~

$n \leq 10^5$，费用流显然超时

考虑对于全过程选取$i$只玩具的总费用$f(i)$，显然它是一个下凸函数，三分求最小值即可

考虑求$f(i)$，对于每天贪心：优先买全新的，否则买最早的慢洗的，还是不行才买最晚的快洗的；

注意不能选最早的快洗的，因为这样可能导致被误选的玩具可以现在不选，以后慢洗而费用更小

开一个关于时间的队列维护即可

#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <queue>
#include <set>
#include <iostream>
typedef long long ll;
#define int long long
using namespace std;
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
const int maxn=3e5+100,inf=1e9;
int t[maxn],n,n1,n2,c1,c2,Tc;
//  remain   ti
pair<int,int> q[maxn];
int qpos[maxn];
inline int min(const int a,const int b){return a<b?a:b;}
inline int f(int x)
{
	int front=1,rear=0,ans=0,corear=0;
	for (int i=1;i<=n;i++)
	{
		int remain=t[i];
		if (x)
		{
			int tmp=min(remain,x);
			ans+=Tc*tmp;
			remain-=tmp;
			x-=tmp;
		}
		while (corear<rear&&q[corear].second+n2<i)++corear;
		while (remain&&front<=rear)
		{
			if (q[front].second+n1<=i)
			{
				int tmp=min(q[front].first,remain);
				ans+=c1*tmp;
				remain-=tmp;
				if (q[front].first==tmp)q[front++].first-=tmp;
				else q[front].first-=tmp;
			}
			else if (corear>=front&&q[corear].second+n2<=i)
			{
				int tmp=min(q[corear].first,remain);
				ans+=c2*tmp;
				remain-=tmp;
				if (q[corear].first==tmp)q[corear--].first-=tmp;
				else q[corear].first-=tmp;
			}
			else break;
		}
		if (remain)return 1e18;
		q[++rear]=make_pair(t[i],i);
	}
	return ans;
}
signed main()
{
	n=read(),n1=read(),n2=read(),c1=read(),c2=read(),Tc=read();
	if (c1>c2)swap(n1,n2),swap(c1,c2);
	if (c1==c2&&n1>n2)swap(n1,n2);
	int sum=0;
	for (int i=1;i<=n;i++)sum+=t[i]=read();
	int l=1,r=sum*Tc;
	while (l+10<r)
	{
		int le=(r-l+1)/3+l,ri=r-(r-l+1)/3+1;
		if (f(le)>f(ri))l=le;
		else r=ri;
	}
	int ans=1e9;
	for (int i=l;i<=r;i++)(ans=min(ans,f(i)));
	printf("%lld\n",ans);
}

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <bitset>

#include <queue>

#include <set>

#include <iostream>

typedef long long ll;

#define int long long

using namespace std;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=3e5+100,inf=1e9;

int t[maxn],n,n1,n2,c1,c2,Tc;

// remain ti

pair<int,int> q[maxn];

int qpos[maxn];

inline int min(const int a,const int b){return a<b?a:b;}

inline int f(int x)

{

int front=1,rear=0,ans=0,corear=0;

for (int i=1;i<=n;i++)

{

int remain=t[i];

if (x)

{

int tmp=min(remain,x);

ans+=Tc*tmp;

remain-=tmp;

x-=tmp;

}

while (corear<rear&&q[corear].second+n2<i)++corear;

while (remain&&front<=rear)

{

if (q[front].second+n1<=i)

{

int tmp=min(q[front].first,remain);

ans+=c1*tmp;

remain-=tmp;

if (q[front].first==tmp)q[front++].first-=tmp;

else q[front].first-=tmp;

}

else if (corear>=front&&q[corear].second+n2<=i)

{

int tmp=min(q[corear].first,remain);

ans+=c2*tmp;

remain-=tmp;

if (q[corear].first==tmp)q[corear--].first-=tmp;

else q[corear].first-=tmp;

}

else break;

}

if (remain)return 1e18;

q[++rear]=make_pair(t[i],i);

}

return ans;

}

signed main()

{

n=read(),n1=read(),n2=read(),c1=read(),c2=read(),Tc=read();

if (c1>c2)swap(n1,n2),swap(c1,c2);

if (c1==c2&&n1>n2)swap(n1,n2);

int sum=0;

for (int i=1;i<=n;i++)sum+=t[i]=read();

int l=1,r=sum*Tc;

while (l+10<r)

{

int le=(r-l+1)/3+l,ri=r-(r-l+1)/3+1;

if (f(le)>f(ri))l=le;

else r=ri;

}

int ans=1e9;

for (int i=l;i<=r;i++)(ans=min(ans,f(i)));

printf("%lld\n",ans);

}

0 0 vote

Article Rating

0 评论

Inline Feedbacks

View all comments