Present（差分裸题）

最小值最大,果断二分

二分之后就是裸题了

遇到第一个不满足二分值的必须要加了,而且是从这个位置开始加

维护用差分就好了

看代码吧,这个没什么好说的

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+10;
int n,m,w;
int a[maxn],b[maxn];
bool isok(int mid)
{
    int ans=0;
    for(int i=0;i<=n+w;i++)    b[i]=0;
    for(int i=1;i<=n;i++)
    {
        b[i]+=b[i-1];
        if( a[i]+b[i]<mid )
        {
            int f = mid-a[i]-b[i];
            b[i]+=f, b[i+w]-=f;
            ans+=f;
        }
        if( ans>m )    return false;
    }
    if( ans<=m )    return true;
    return false;
}
signed main()
{
    cin >> n >> m >> w;
    for(int i=1;i<=n;i++)    cin >> a[i];
    int l=0,r=2e9,mid,ans=0;
    while( r>=l )
    {
        mid = l+r>>1;
        if( isok(mid) )    l=mid+1,ans=mid;
        else    r=mid-1;
    }
    cout << ans ;
}