【二分查找】机器人跳跃问题

题目

730. 机器人跳跃问题 - AcWing题库

---

机器人正在玩一个古老的基于 DOS 的游戏。

游戏中有 $N+1$ 座建筑——从 $0$ 到 $N$ 编号，从左到右排列。

编号为 $0$ 的建筑高度为 $0$ 个单位，编号为 $i$ 的建筑高度为 $H(i)$ 个单位。

起初，机器人在编号为 $0$ 的建筑处。

每一步，它跳到下一个（右边）建筑。

假设机器人在第 $k$ 个建筑，且它现在的能量值是 $E$ ，下一步它将跳到第 $k+1$ 个建筑。

如果 $H(k+1)>E$ ，那么机器人就失去 $H(k+1)-E$ 的能量值，否则它将得到 $E-H(k+1)$ 的能量值。

游戏目标是到达第 $N$ 个建筑，在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式

第一行输入整数 $N$ 。

第二行是 $N$ 个空格分隔的整数， $H(1),H(2),…,H(N)$ 代表建筑物的高度。

输出格式

输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围

$1 \le N,H(i) \le 10^5$ ,

输入样例1：

5
3 4 3 2 4

输出样例1：

4

输入样例2：

3
4 4 4

输出样例2：

4

输入样例3：

3
1 6 4

输出样例3：

3

解题

方法一：二分查找

思路

二分初始能量的最小值，即二分左边界。

二分 check 的过程中要注意的是：由于能量每次的变化量是 $e - h[i]$ ，所以当 $e$ 比 $h[i]$ 大一个数量级或以上时 $e$ 会很快地开始指数级增长（此时 $e$ 每次的增长量相当于它自身），此时 $e$ 将会很快地整型溢出甚至长整型溢出随后导致 check() 函数返回错误，所以当 $e$ 比 $max(h[0\dots n])$ 大时就可以认定此初始能量可行，直接返回 true 即可。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n, mx;
    static int[] h;
    
    static boolean check(long e) {
        for (int i = 0; i < n; ++i) {
            e += e - h[i];
            if (e < 0) return false;
            if (e >= mx) return true;
        }
        return e >= 0;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        h = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            h[i] = (int) in.nval;
            mx = Math.max(mx, h[i]);
        }
        int l = 0, r = mx;
        while (l < r) {
            int m = l + r >> 1;
            if (check(m)) r = m;
            else l = m + 1;
        }
        System.out.println(l);
    }
}