分析

经典的字眼，要求最小值最大。考虑二分答案。如何判断合法性。对于二分出来的最小值。从左向右扫一次，在考虑 时，我们已经保证 是一个合法的区间了，所以只有向后加才有意义。所以遇到小于二分出来的数时，直接 这个区间 。用差分数组维护一下就好了，当操作次数大于 时是不合法答案，时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define LL int
LL read() {LL x;scanf("%d",&x);return x;}
LL A[N],C[N],n,m,w; 
bool check(LL x) {
    LL tot = 0;memset(C,0,sizeof(C));
    for(int i = 1;i <= n;i++) {
        C[i] = C[i] + C[i-1];
        if(A[i] + C[i] < x) {
            LL c = x-A[i]-C[i];
            tot+=c;C[i]+=c;
            if(i+w <= n) C[i+w]-=c;
            if(tot > m) return false;
        }
    }
    return tot <= m;
}
int main() {
    n = read();m = read();w = read();
    for(int i = 1;i <= n;i++) A[i] = read();
    LL l = 1,r = (1<<30),ans = 0;
    while(l <= r) {
        LL mid = l + r >> 1;
        if(check(mid)) l = mid + 1,ans = max(ans,mid);
        else r = mid - 1;
    }
    printf("%d\n",ans);
    return 0;
}