2019字节笔试-526互联

机器人跳跃问题

机器人正在玩一个古老的基于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

输出例子：

示例2

输入例子：

3
4 4 4

输出例子：

示例3

输入例子：

3
1 6 4

这道题目可以用二分正着推过去，不过要注意，需要进行剪枝，因为公式是E -(H-E) 如果此时E已经是数组中的最大值的情况，后面肯定是true了，因为H-E是负数，每次模拟下去肯定是越来越大的，所以可以直接退出
代码如下

package com.execise.test1093;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zhs
 * @date 2023/5/27
 */
public class Testnewke7 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            ArrayList<Integer> list= new ArrayList<Integer>();
            int max=0;
            for(int i=0;i<a;i++){
                list.add(in.nextInt());
                max=Math.max(list.get(i),max);
            }

            int left=0;
            int right= max;
            int res=-1;
            while(left<=right){
                int mid=left+(right-left)/2;

                if(canSuccess(list,mid)){
                    res=mid;
                    right=mid-1;
                }else{
                    // 太小了
                    left=mid+1;
                }
            }
            System.out.println(res);
        }
    }

    public static boolean canSuccess(ArrayList<Integer> list,long start){

        int max=0;
        for (int i = 0; i < list.size(); i++) {
            max=Math.max(max,list.get(i));
        }
        for(int i=0;i<list.size();i++){

            long t=start-(list.get(i)-start);
            if(t<0){
                return false;
            }
            if (t>=max){
                return true;
            }
            start=t;
        }




        return true;
    }
}