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

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

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

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

 

 

 

emodelpapers.in 说:
2023年4月22日 22:46

Emodelpapers.in Board EModel Paper 2023 Aspirants who had Registered for the Board 12th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. emodelpapers.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.


登录 *


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