CodeVS 1513 皇帝的烦恼 【二分】

tonyfang posted @ 2015年10月09日 09:45 in codevs with tags c++ OI , 421 阅读

好久没写博客了~

这几天开始停课训练了,先来做题目。

题目链接:http://codevs.cn/problem/1513/

【题解】二分,计算每个几何与第一个几何的并集的元素个数上下界即可。复杂度O(nlogn)。

# include <stdio.h>
# include <algorithm>
using namespace std;
int n,a[20010],s,l,r,left[20010],right[20010];
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	s=a[1];
	for (int i=2;i<=n;++i)
		s=max(s,a[i]+a[i-1]);
	left[1]=a[1],right[1]=a[1];
	l=s,r=s+s;
	while(l<r) {
		int mid=l+r>>1;
		for (int i=2;i<=n;++i) {
			left[i]=max(0,a[1]+a[i-1]+a[i]-mid-right[i-1]);
			right[i]=min(a[i],a[1]-left[i-1]);
		}
		if(left[n]==0) r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}

登录 *


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