【题解】Present

题目：https://ac.nowcoder.com/acm/problem/110615
题意：给定a数组，可操作m次让w个连续的位置+1，问最大化的最小值是多少。
分析：
明显，最小值越大越难满足，满足单调性，考虑二分；
check就从前往后考虑当前位置是否满足最小，不满足则选择以当前位置为连续区间的开始w连续个加1（这里我用线段树怎么都过不了。。）用BIT实现。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define MP make_pair
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
typedef long long ll;
const int mod=1e9+7;
const int M=2e5+5;
const int inf=0x3f3f3f3f;
const ll INF=1e18;
int n,w;
int m;
int a[M];
struct BIT{
    int tr[M];
    void init(int x){
        for(int i=0;i<=x;i++)
            tr[i]=0;
    }
    void add(int i,int val){while(i<=n)tr[i]+=val,i+=(i&-i);}
    int sum(int i){
        int res=0;
        while(i)
            res+=tr[i],i-=(i&-i);
        return res;
    }
}t1;
bool check(int midd){

    int sum=0;
    for(int i=1;i<=n;i++){
        int now=t1.sum(i);
        if(now<midd){
            t1.add(i,midd-now);
            t1.add(i+w,now-midd);
            sum+=midd-now;
        }
        if(sum>m)
            return false;
    }
    return true;
}
int main(){
    scanf("%d%d%d",&n,&m,&w);
    int l=inf,r=0,ans;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        l=min(l,a[i]);
        r=max(r,a[i]);
    }
    l--,r+=m+1;
    while(l<=r){
        t1.init(n);
        for(int i=1;i<=n;i++)
            t1.add(i,a[i]-a[i-1]);
        int midd=(l+r)>>1;
        if(check(midd)){
            ans=midd;
            l=midd+1;
        }
        else
            r=midd-1;
    }
    printf("%d\n",ans);
    return 0;
}