Plants vs. Zombies （ZOJ - 4062，二分答案 + 细节）

一.题目链接：

ZOJ-4062

二.题目大意：

n 个植物排成一排.

水壶只能移动 m 步.

水壶一步移动一个单位长度，所到达的位置，该植物的防御值会相应增加.

求浇水之后，所有植物防御值中最小值最大可以为多少.

三.分析：

二分答案即可.

不过要加限制条件，在 check(mid) 函数中 cnt 可能会暴 long long.

这是因为，假设 n == 1e5，mid == 1e17 ，a[i] 均为 1.

此时，cnt 为 1e22.

所以要在 cnt 超过 mid后，立即 return 0.

中间用滚动数组 f 和 s 分别代表当前和下一株植物的防御值.

还有就是要特判一下最后一株植物.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;
const int M = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;

int n;
ll m;
int a[M + 5];

bool check(ll mid)
{
    ll f, s, x;
    f = s = 0;
    ll cnt = 0;
    int pos = 0;
    for(int i = 1; i < n; ++i)
    {
        if(cnt > m)
            return 0;
        if(pos == i - 1)
        {
            s += a[i];
            cnt++;
            pos = i;
            f = s;
            s = 0;
        }
        if(pos == i)
        {
            x = mid - f;
            if(x <= 0)
                continue;
            x = x / a[i] + !(x % a[i] == 0);
            cnt += 2 * x;
            s = a[i + 1] * x;
        }
    }
    if(s < mid)
    {
        x = mid - s;
        x = x / a[n] + !(x % a[n] == 0);
        cnt += 2 * x - !(pos == n);
    }
    return cnt <= m;
}

/**
1
3 8
59 6 97

24
**/

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        scanf("%lld", &m);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        ll l = 0;
        ll r = 1e18;
        ll mid;
        while(l < r)
        {
            mid = (l + r + 1) >> 1;
            if(check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        printf("%lld\n", r);
    }
    return 0;
}