机器人跳跃问题 #

题目 #

机器人正在玩一个古老的基于 DOS 的游戏。游戏中有 N+1 座建筑——从 0 到 N 编号，从左到右排列。编号为 0 的建筑高度为 0 个单位，编号为 i 的建筑的高度为 H(i) 个单位。 起初， 机器人在编号为 0 的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第 k 个建筑，且它现在的能量值是 E, 下一步它将跳到第个 k+1 建筑。它将会得到或者失去正比于与 H(k+1) 与 E 之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将得到 E - H(k+1) 的能量值。 游戏目标是到达第个 N 建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？

格式：

输入：

• 第一行输入，表示一共有 N 组数据.
• 第二个是 N 个空格分隔的整数，H1, H2, H3, ..., Hn 代表建筑物的高度 输出：
• 输出一个单独的数表示完成游戏所需的最少单位的初始能量 示例 1：

输入： 5 3 4 3 2 4 输出：4 示例 2：

输入： 3 4 4 4 输出：4 示例 3：

输入： 3 1 6 4 输出：3 提示：

1 <= N <= 10^5 1 <= H(i) <= 10^5

公式推导 #

假设当前剩余能量E，下一个楼的高度为 H(k+1)，

• 如果 H(k+1) > E，那么将失去 H(k+1) - E的能量，剩余能量 E - (H(k+1) - E) = 2 * E - H(k+1)
• 如果 H(k+1) < E，那么将得到 E - H(k+1)的能量，剩余能量 E + (E - H(k+1)) = 2 * E - H(k+1)

于是我们只需保证每次跳跃之后剩余的能量2 * E - H(k+1)大于等于0即可。

如果我们要保证最后一次跳跃之后能量数大于等于0，那么倒数第二次跳跃之后能量要大于等于 (H(len - 1) + 0 + 1) / 2

前一层所需要的最小能量 =（当前层的高度 + 当前层所需最小能量 + 1）/ 2

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
        int res = func(arr);
        System.out.println(res);
    }
    public static int func(int[] arr){
        int res = 0;
        for(int i = arr.length - 1; i >= 0; i--){
            // +1是因为需要向上取整
            res = (arr[i] + res + 1) / 2;
        }
        return res;
    }
}