NC110615（Present ）

感受

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, m, w;
int a[maxn];
ll sum[maxn];
int lowbit(int x){
    return x & (-x);
}
void add(int i, int x){
    while(i <= n){
        sum[i] += x;
        i += lowbit(i);
    }
}
ll getsum(int i){
    ll ans = 0;
    while(i){
        ans += sum[i];
        i -= lowbit(i);
    }
    return ans;
}
bool check(ll v){
    for(int i = 1; i <= n; i++){
        sum[i] = 0;
    }
    for(int i = 1; i <= n; i++){
        add(i, a[i] - a[i - 1]);
    }
    ll num = 0;
    for(int i = 1; i <= n; i++){
        ll k = getsum(i);
        if(k < v){
            k = v - k; num += k;
            if(num > m) return false;
            add(i + w, -k);
            add(i, k);
        }
    }
    return true;
}
int main(){
    ll l, r, mid; l = 1; r = 2e9;
    scanf("%d%d%d", &n, &m, &w);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    while(r - l > 1){
        mid = (l + r) / 2;
        if(check(mid)){
            l = mid;
        }
        else{
            r = mid;
        }
    }
    printf("%lld\n", l);
    return 0;
}