CodeVS 1513 皇帝的烦恼 【二分】

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

好久没写博客了~

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

题目链接: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;
}
https://epfuanlogin. 说:
2023年4月15日 22:38

According to the EPF India new Interest rates will down maybe for this 2019 financial year, and the new interest rates will be announced on February 2019, and previous year's interest rate of 8.55 percent for the 2017-18 financial and 8.65 percent for the 2016-17 and 8.8 percent in 2015-16, that’s why we https://epfuanlogin.com/ have expected this 2019 financial year also will decrease than previous years.The Employees’ Provident Fund Organisation of India has provided services for all employees and employers of government and private authorities, and they have provided very good interest rates on deposits and long-term retirement savings.

boardmodelpaper.com 说:
2024年1月03日 20:56

Board Model Papers 2024 provide all states of 6th to 10th text books 2024 Candidates who are Searching for 6th to 10th and 11th to 12th text books and syllabus, sample questions, exam pattern, and Co-Curricular Subject textbooks can refer to this entire article. boardmodelpaper.com and question papers for following the website and Arts, Science, Commerce Stream Subject Wise Solved Question Bank for Hindi & English Medium Students with Exam Pattern & Blueprint and subject Wise with 11th & 12th Question Bank 2024 for General & Vocational Course. Here, we have gathered all subjects of Board textbooks for all Class along with the direct download links.


登录 *


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