Codeforces 460C Present(二分)

题目链接：Codeforces 460C Present

题目大意：有n盆花，可以浇m次水，每次浇水的范围为w，被浇到水的花长高1米，问说可以使最矮的花的最高值是多少

解题思路：二分答案，遍历判断一遍。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1e5+5;
const int inf = 1e9+maxn;

int N, M, W, arr[maxn], v[maxn];

bool judge (int k) {
    int ti = M, n = 0;
    memset(v, 0, sizeof(v));

    for (int i = 1; i <= N; i++) {
        n += v[i];
        int tmp = max(k - arr[i] - n, 0);

        ti -= tmp;
        if (ti < 0)
            return false;

        if (i + 1 <= N)
            v[i+1] += tmp;
        if (i + W <= N)
            v[i+W] -= tmp;
    }
    return true;
}

int bsearch (int l, int r) {
    for (int i = 0; i < 80; i++) {
        int mid = (r + l) / 2;
        if (judge(mid))
            l = mid;
        else
            r = mid;
    }
    return l;
}

int main () {
    scanf("%d%d%d", &N, &M, &W);
    for (int i = 1; i <= N; i++)
        scanf("%d", &arr[i]);
    printf("%d\n", bsearch(1, inf));
    return 0;
}