• 前言

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

  • 分析

    这道题的话,通过二分最小的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;
    }