2018 青岛ICPC区域赛E Plants vs. Zombies

E Plants vs. Zombies
题意： 从左到右依次是1个房子+n个植物，从房子出发给n个植物浇水，每一次可以往左可以往右，起始时植物的防御值都为0，每一次在i位置浇一次水，防御增加d[i]，每一次必须走，不能呆在原地，可以走出去，定义n个植物的防御力为 $min\left(a_i\right)1\&lt;=i\&lt;=n$min(ai​)1<=i<=n,问怎样走使得这些植物防御力最小值最大
分析： 最大化最小值，肯定是二分答案的值，关键是在于如何写好check函数，即采用什么样的策略
贪心策略如下：

1. 计算在当前mid下，至少需要经过该点多少次
2. 从左往右扫一遍
3. 走到当前位置，需要走一步，m–，然后看还需要多少步，假设需要走cnt步，那么就选择走到下一个节点然后在走过来，共需要2*cnt步，什么时候m为0就停止
   为什么这个贪心策略是正确的，因为任何方案都可以等价为在两个点来回跳转

const int maxn = 1e5+100;
LL a[maxn];
LL d[maxn];
LL c[maxn];
LL n,m;
bool check(LL mid,LL m){
    if(mid == 0) return true;
    for(int i = 1;i <= n; ++i){
        c[i] = (mid-1)/d[i]+1;
        a[i] = 0;
    }
    for(int i = 1;i <= n; ++i){
        if(i == n && a[i] >= c[i]) return true;
        if(m <= 0) return false;
        a[i] += 1,m--;
        if(a[i] >= c[i]) continue;
        // if(c[i]-a[i] > m)
        LL cnt = c[i]-a[i];
        if(2*cnt > m) return false;
        m -= 2*cnt;
        a[i+1] += cnt; 
    }
    return true;

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