$$\color{Red}{机器人跳跃问题【二分】（java递推方法和二分方法）}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

机器人正在玩一个古老的基于 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 ≤ N, H(i) ≤ 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

二分证明

首先很关键的一个事情——》怎么计算能量变化：
当跳跃到更高的一个台阶：E - (h - E) = 2E - h
当跳跃到更低的一个台阶：E + (E - h) = 2E - h
发现不管高度如何 能量的计算公式是不变的

我们显然根据数学归纳法可以得知
E1, E2, ***, En
E'1, E'2, ***, E'n
当初始能量更大的情况下，根据公式可知 E2也会大于E‘2，最终能量更大，因此我们观察到了单调性，我们就可以利用这个性质进行二分

当E满足条件的情况下，根据计算可以得知会递增，若E大于了最高的max-h，根据
2E - h = E + E - h >= E + max_h - h > 0
此时有可能产生爆int的情况，我们可以提前在这里进行剪枝 直接判定满足条件

递推证明

一个很符合正常人的思路，最符合答案的解应该是满足最终体力为0的情况，我们通过倒推之前的公式
E1 = 2E0 - h --> E0 = E1 + h >> 1
从最终为0体力倒推之前的体力值应该是多少，为了避免出现int的向下取整，如果为奇数我们就进行加1操作

java

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

public class Main {
    static int n, N = 100010;
    static int h[] = new int [N];

    public static boolean check(int x){
        for(int i=1; i<=n; i++) {
            x = x * 2 - h[i];
            if (x >= (int) 1e5) return true;
            if (x < 0) return false;
        }
        return true;
    }

    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        for(int i=1; i<=n; i++) h[i] = Integer.parseInt(s[i-1]);

        int l = 0, r = (int)1e5;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        System.out.println(l);
    }
}