Present

题目大意:

先给你一串序列,你至多有\(\text{m}\)次操作使得一段长度为\(w\)的区间加一

问这串序列的最小值最大可以是多少?

分析:

最小值最大或者最大值最小,我们的第一反应可能都是二分答案 > 简单证明一下: > > 如果最小值最大为\(x\),那么只要我们少做一次操作,那么\(x-1\)也是可行的 > > 这满足二分答案的性质,所以呢二分答案没有问题的

那么关于\(check\)函数的话,如果当前我们枚举到的数他小于这个我们\(\text{check}\)的值,那么我们就给这一段区间加上这个差值(如果可以加,否则返回零)

那么时间复杂度大概就是\(O(\log10^9*n)\),可以接受的

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

ll n, m, w, a[maxn];
ll CF[maxn], temp[maxn];
ll l(0x7fffffff), r, ans;

inline bool Check(ll x) 
{
    memcpy(temp + 1, CF + 1, sizeof(ll) * n);
    ll now(0), rest(m);
    for (ll i = 1; i <= n; ++i) {
        now += temp[i];
        if (now >= x) continue;
        if (now + rest < x) return 0;
        ll get = x - now;
        rest -= get;
        now += get;
        if (i + w <= n) temp[i + w] -= get;
    }
    return 1;
}

signed main()
{
    n = __read(), m = __read(), w = __read();
    for (ll i = 1; i <= n; ++i)  {
        a[i] = __read();
        CF[i] = a[i] - a[i - 1];
        l = min(l, a[i]), r = max(r, a[i]);
    }
    r += m;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (Check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    printf ("%lld\n", ans);
    system("pause");
}