Plants vs. Zombies【二分】

ZOJ - 4062 Plants vs. Zombies

BaoBao and DreamGrid are playing the game Plants vs. Zombies. In the game, DreamGrid grows plants to defend his garden against BaoBao’s zombies.

题意：植物大战僵尸

一个长度为 $n$ 的数组 $array[1,n]$，初始值为0，每个元素有各自的增长速度$a[i]$。从数组的最左侧 $array[0]$ 开始，每次可以左右移动一步（移动范围不限）。如果移动到位置$i$，那么 $array[i]$ 增加 $a[i]$。问移动m步，该序列中的最小值的最大值是多少。

思路：

最大化最小值，我们可以二分答案。二分到最小值的最大值是 x 的时候，我们需要求出每个元素值达到 x 至少需要多少步，如果$array[i]$达到 x 需要 k 步，那么$array[i+1]$就是已经走过了 k-1 步的。
注意：有可能会因为为了达到前一个元素的步数，而导致后一个元素的步数已经达到了 x，如果该元素不是最后一个元素，那么我们继续往后走，该元素仍需要多走一步；否则我们直接判断所有步数是否在 m 步内，并返回即可。【代码后附的样例可参考】

Code:

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxN = 100005;

ll read()
{
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -f; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

ll n, m;
ll a[maxN];
ll s[maxN];

bool judge(ll x)
{
    memset(s, 0, sizeof(s));
    ll tot = 0;
    for(int i = 0; i < n; ++ i ) {
        if(tot > m) return false;
        ll still = x - s[i] * a[i];
        ll need;
        if(still <= 0) {
            if(i == n - 1) return tot + s[i] <= m;
            need = 1;
        } else {
            need = still / a[i] + ll(still % a[i] != 0);
        }
        s[i] += need;
        s[i + 1] += need - 1;
        tot += s[i];
    }
    return tot + s[n] <= m;
}

int main() {
    int t; scanf("%d", &t);
    while(t -- ) {
        n = read(); m = read();
        ll l = INF, r = 0, ans;
        for(int i = 0; i < n; ++ i ) {
            a[i] = read();
            l = min(l, a[i]);
            r = max(r, a[i]);
        }
        if(m < n) {
            printf("0\n");
            continue;
        }
        r *= m;
        while(l <= r) {
            ll mid = (l + r) >> 1;
            if(judge(mid)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}
/*
2
4 8
3 4 5 6
2 3
1 2
 */