CF 460C Present 【DP+】主意

给你n高树花。m日，每天连续浇筑w鲜花。一天一次，花长1高度单位

求m天后。最矮的花最高是多少

最大最小问题能够用二分来解

首先我们能够得到全部花的最矮高度即答案的下界，给这个花浇m天即是答案的上界

然后二分枚举答案，检验合法性。

怎样检验合法性

我们用个数组来记录need[i]表示
i点须要浇的次数（从i点開始的区间）

我们再用一个变量has来维护
i点已经被浇了的次数（由i点之前的在浇花范围内的点浇过的次数和）

动态地维护这两个值就可以

假设不够浇的。need[i]前缀和已经大于m天。则return false;

不然 return true;

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

using namespace std;

const int NN=111111;

int n,m,w;

int need[NN];

int f[NN];

bool can(int s){

	int a=0;int b=m;

	for(int i=1;i<=n;i++){

		if(i>=w)

			a-=need[i-w];

		need[i]=max((int)0,s-a-f[i]);

		a+=need[i];

		b-=need[i];

		if(b<0)

			return false;

	}

	return true;

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("G:/in.txt","r",stdin);

	//freopen("G:/myout.txt","w",stdout);

#endif

	cin>>n>>m>>w;

	int minn=(1<<30);

	for(int i=1;i<=n;i++){

		cin>>f[i];

		minn=min(f[i],minn);

	}

	int maxn=minn+m;

	int mid=(minn+maxn)/2+1;

	while(minn<maxn){

		if(can(mid)){

			minn=mid;

		}else{

			maxn=mid-1;

		}

		mid=(minn+maxn)/2+1;

	}

	cout<<minn<<endl;

}