#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
//yr
typedef long long ll;
ll n,m,w;
ll num[100005];
ll need[100005];
ll v[100005]; //v数组用来存放标识 若下标超过他 则对watered操作 意为 变为 未浇水状态
int main()
{
while(scanf("%lld %lld %lld",&n,&m,&w)==3)
{
ll Min=0x3f3f3f3f,Max=-1;
ll ans;
for(int i=0;i<n;i++)
{
scanf("%lld",&num[i]);
if(num[i]>Max)
{
Max=num[i];
}
if(num[i]<Min)
{
Min=num[i];
}
}
Max+=m; // 最大查找 Max+m 意为最大高度 并且 浇了m天的水
ll l=Min,r=Max;
while(l<=r)
{
// cout << ans << endl;
memset(v,0,sizeof(v));// // 浇过花的标记 过了这个标记则将watered去除相应
ll mid=(l+r)/2;
for(ll i=0;i<n;i++)
{
need[i]=max(mid-num[i],ll(0)); //意为 到答案为止 还需浇多少天水
}
ll watered=0;//已经浇水天数
ll restday=m;//距离截止日期还有天数
for(int i=0;i<n;i++)
{
watered+=v[i]; //v[i]为负值 意为 距离 x朵花区间已过
need[i]-=watered; //在浇水区间内 减去浇水天数
if(need[i]>0)
{
restday-=need[i];
if(restday< 0 ) break;
watered+=need[i];
v[i+w]-=need[i];
need[i]=0;
}
}
if(restday<0)
r=mid-1;
else
{
ans=mid;
l=mid+1;
}
}
printf("%lld\n",ans);
}
}
这道题 我一想到就是二分 ，但是一开始想到的是二分查找最小高度的花，这样并不满足二分查找单调性。
于是二分查找 答案，难点应该在于v数组的标记使用。 如果想明白了，就很简单。
其他博客亦有使用前缀和数组替代。
