Acwing：730. 机器人跳跃问题（二分法）

问题描述：

题目链接：730. 机器人跳跃问题
机器人正在玩一个古老的基于 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` = E - (H(k+1)−E) = 2E - H(k+1)

如果获得能量，则获得后的总能量： E` = E + (E−H(k+1)) = 2E - H(k+1)

所以能量的变化为 E` = 2E - H(k+1)

E越大 能量变化越大 可得出具有单调性 可以用二分求解

二分法：

二分法求解的是E的取值，E的取值范围在0到10**5之间，存在最小的E使E的左边不满足条件（也就是在跳跃时E会小于0），E的右边都是满足条件的E。

判断E是否符合可以用E的变化公式E` = 2E - H(k+1)来判断

代码及详细注释：

n = int(input())  # 输入一个整数n
nums = list(map(int, input().split()))  # 输入n个整数，存储在列表nums中

# 定义一个函数check，用于检查给定的值e是否满足条件
def check(e):
    for i in range(n):
        e = 2 * e - nums[i]  # 更新e的值
        if e < 0:  # 如果e小于0，则返回False
            return False
    return True  # 如果所有元素都满足条件，则返回True

l = 0  # 初始化左边界为0
r = 10 ** 5  # 初始化右边界为10^5
while l < r:
    mid = (l + r) // 2  # 计算中间值mid
    if check(mid):  # 调用check函数检查mid是否满足条件
        r = mid  # 如果满足条件，则将右边界更新为mid
    else:
        l = mid + 1  # 如果不满足条件，则将左边界更新为mid+1
print(l)  # 输出最终结果l

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21