Present

前言

刚开始什么思路都没有，但是突然想到了一道题——换教室，似乎也是二分，然后运用到这一道题，似乎就明了了

分析

这道题的话，通过二分最小的w，是每一盆花的a[i]>=w，并且浇的天数小于等于m。这就是主要思路。

实现

题目中给出了一个w(刚开始我也不知所措啊QwQ)，然而我们想一想，设一个f[i]表示将[i,i+w-1]区间浇水的天

数，那么之后对于一个j，因为之前的第j-w盆肯定浇过，那么就可以减去那一盆的贡献，然后求出对于第j盆是否

还需要再浇。

代码

/*二分加差分*/
/*
每次二分一个最小值，算出使每一个a
都大于它至少要浇多少次，而之前(i-w)如果
有浇过，那么可以减去那一次的次数 
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#define R register
#define ll long long
#define inf INT_MAX
using namespace std;
const int N=1e5+10;
ll n,m,w;
ll a[N],f[N];
bool check(ll k)
{
ll rem=m,us=0;
//还剩下的，已经用过的 
for (int i=1;i<=n;i++)
{
    if(i>=w) us-=f[i-w];
    //说明之前这个区间浇过水了
    f[i]=max((ll)0,k-us-a[i]);
    us+=f[i];
    rem-=f[i];
    if(rem<0) return 0; 
}
return 1;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&w);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);

ll l=1,r=1e15,ans=0;
while(l<=r)
{
    int mid=(l+r)>>1;
    if(check(mid)) ans=mid,l=mid+1;
    else r=mid-1;
}

printf("%lld\n",ans);

return 0;
}