问题 A: [USACO2008 Nov]toy 玩具
时间限制: 1 Sec 内存限制: 162 MB
题目描述
玩具 [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已经了解到节约的意义. 帮助她找到提供玩具的最便宜的方法.
输入
* 第 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
输入解释:
Bessie想开4天的party, 第1天需要8个玩具, 第2天需要2个玩具, 第3天需要1个玩具,
第4天需要6个玩具. 第一种方式需要 2,用时1天;第二种方式需要 1, 用时2天. 买
一个玩具需要 3.样例输出35输出解释:第1天买8个玩具,花去 24; 送2个玩具去快洗, 6个慢洗.
第 2 天 取回2个快洗的玩具, 花去 4.送1个玩具去慢洗.第3天取回6个慢洗的玩具,花去 6.
第 4 天 取回所有的玩具(与现有的加在一起正好6个), 花去$1. 这样就用了最少的钱.
这明显是网络流里的”餐巾问题“。
但这明显TLE.
其实还有另一个做法：就是贪心。
而贪心的答案满足单峰性质。证明：
设x为买的玩具数，f(x)为花的总钱数，g(x)为洗玩具花的钱数，
那么，f（x）=g(x)+tc*x;
而对于g，很明显x越大，g(x)越小。而且g(x)-g(x-1)<=g(x+1)-g(x)当前多洗一个可能是便宜的，而再多洗一个可能就是要贵洗了。。。
因此f数组满足同样的性质，于是斜率递增，然后他就单峰了。
那么来说一下贪心。首先，如果便宜的用时比贵的还要短，那就没必要选贵的了。
慢的从前向后找，快的从后往前找。如果快的也从前往后找会被卡掉的。也就是说，能用慢的先用慢的，慢的用光了再用快的。。。。
但是找的时候要优化一下：
1，可以用两个队列。
2，从前向后找用一个指针，从后向前用一个并查集。
#pragma GCC optimize("O3")
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100005
using namespace std;
int d,n1,n2,c1,c2,t,a[N],sum[N],f[N];
int read()
{int sum=0,f=1;char x=getchar();while(x<'0'||x>'9'){
if(x=='-')f=-1;x=getchar();}while(x>='0'&&x<='9'){
sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}return sum*f;
}
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);}
inline int check(int x)
{int s=x*t,top1=1,top2=0;for(int i=1;i<=d;i++)sum[i]=a[i],f[i]=i;for(int i=1;i<=d;i++){int k=sum[i];if(x>=k){x-=k;k=0;continue;}else k-=x,x=0;top2=i-n2;while(top1<=i-n1){if(sum[top1]>=k){
sum[top1]-=k;s+=k*c1;k=0;break;}else{k-=sum[top1];s+=sum[top1]*c1;sum[top1]=0;top1++;}}if(k==0)continue;while(top1<=top2){if(sum[top2]>=k){
sum[top2]-=k;s+=k*c2;k=0;break;}else{k-=sum[top2];s+=sum[top2]*c2;sum[top2]=0;f[top2]=find(top2-1);top2=f[top2];}}if(k>0)return 1000000000;}return s;
}
int main()
{//freopen("toy.in","r",stdin);//freopen("toy.out","w",stdout);scanf("%d%d%d%d%d%d",&d,&n1,&n2,&c1,&c2,&t);int h=0;if(n1<n2){swap(n1,n2);swap(c1,c2);}if(c1>c2)c1=c2,n1=n2;for(int i=1;i<=d;i++)a[i]=read(),h+=a[i];int l=1,r=h,mid,mmid,ans=1000000000;while(l<=r-3){int k=r-l+1;mid=l+k/3;mmid=l+(k*2)/3;int s1=check(mid),s2=check(mmid);if(s1<s2)r=mmid;else l=mid;}for(int i=l;i<=r;i++)ans=min(ans,check(i));printf("%d\n",ans);
}