【CodeForces - 460C】Present（二分+树状数组）

题干：

给定N朵花的原先的高度，从左到右排列，最多浇水m天，每天只能浇一次，每次使得连续的w朵花的高度增长1，问最后最矮的花的高度最高是多少。

Examples

Input

6 2 3
2 2 2 2 1 1

Output

2

Input

2 5 1
5 8

Output

9

Note

In the first sample beaver can water the last 3 flowers at the first day. On the next day he may not to water flowers at all. In the end he will get the following heights: [2, 2, 2, 3, 2, 2]. The smallest flower has height equal to 2. It's impossible to get height 3 in this test.

解题报告：

  直接二分即可。树状数组差分维护区间更新，复杂度O(nlognlogn)，其实可以优化到nlogn，直接用一个变量维护增量即可。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 4e5 + 5;
ll n,m,w,a[MAX];
ll c[MAX];
int lowbit(int x) {return x&-x;}
ll sum(int x) {
	ll res = 0;
	while(x) {
		res += c[x];
		x -= lowbit(x);
	} return res;
}
void update(int x,ll val) {
	while(x < MAX) {
		c[x] += val;
		x += lowbit(x);
	}
}
bool ok(ll x) {
	ll cnt = 0,tmp;
	for(int i = 1; i<=n+w+1; i++) c[i]=0;
	for(int i = 1; i<=n; i++) {
		tmp = sum(i);
		if(a[i] + tmp < x) {
			cnt += (x-a[i]-tmp);
			update(i,x-a[i]-tmp);update(i+w,-(x-a[i]-tmp));
		}
	} return cnt <= m;
}
int main()
{
	cin>>n>>m>>w; 
	for(int i = 1; i<=n; i++) scanf("%lld",a+i);
	ll l = 0,r = 2e9,mid,ans;
	while(l<=r) {
		mid = (l+r)>>1;
		if(ok(mid)) l = mid+1,ans = mid;
		else r = mid-1;
	}
	printf("%lldn",ans);
	return 0 ;
}

最后

以上就是欣慰蛋挞为你收集整理的【CodeForces - 460C】Present（二分+树状数组）的全部内容，希望文章能够帮你解决【CodeForces - 460C】Present（二分+树状数组）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。