BZOJ 1229 [USACO2008 Nov]toy 玩具 【三分+贪心】

tonyfang posted @ 2016年2月26日 16:55 in BZOJ with tags c++ OI , 300 阅读

【题解】三分后贪心即可。

# include <stdio.h>
# include <stdlib.h>
# include <vector>
# include <queue>
# include <deque>

using namespace std;

const int M=300010,setEps=5,Inf=2000113000;
int n,n1,n2,c1,c2,tc,d[M],all=0;
deque< pair<int,int> > p,q,t;

inline int get(int x) {
	p.clear(); q.clear(); t.clear();
	int ret=(tc-c2)*x;
	p.push_back(make_pair(0,x));
	for (int i=1;i<=n;++i) {
		while(!t.empty() && i-t.front().first>=n1)
			q.push_back(t.front()),t.pop_front();
		while(!q.empty() && i-q.front().first>=n2)
			p.push_back(q.front()),q.pop_front();
		int gg=d[i];
		while(gg) {
			if(!p.empty()) {
				if(p.back().second>gg) {
					p.back().second-=gg;
					ret+=gg*c2;
					gg=0;
				}
				else {
					gg-=p.back().second;
					ret+=p.back().second*c2;
					p.pop_back();
				}
			} else if(!q.empty()) {
				if(q.back().second>gg) {
					q.back().second-=gg;
					ret+=gg*c1;
					gg=0;
				} else {
					gg-=q.back().second;
					ret+=q.back().second*c1;
					q.pop_back();
				}
			} else return Inf;
		}
		t.push_back(make_pair(i,d[i]));
	}
	return ret;
}

int main() {
	scanf("%d%d%d%d%d%d",&n,&n1,&n2,&c1,&c2,&tc);
	for (int i=1;i<=n;++i) scanf("%d",&d[i]), all=all+d[i];
	if(n1>n2) {
		swap(n1,n2);
		swap(c1,c2);
	}
	if(c1<c2) c2=c1;
	int l=0, r=all;
	while(1) {
		if(r-l <= setEps) {
			int t=Inf;
			for (int i=l;i<=r;++i) t=min(t,get(i));
			printf("%d\n",t);
			return 0;
		}
		int mid1=l+(r-l)/3, mid2=l+(r-l)*2/3;
		int gmid1=get(mid1),gmid2=get(mid2);
		if(gmid1 != Inf && gmid1<=gmid2) r=mid2;
		else l=mid1;
	}
	return 0;
}

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter