首页 > 试题广场 >

机器人跳跃问题

[编程题]机器人跳跃问题
  • 热度指数：17118 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
机器人正在玩一个古老的基于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
算法知识视频讲解
添加回答
Java
lyongwolf头像 lyongwolf
逆天不给数据范围的会爆long的题。。。二分本来明显，确这么搞心态。tips：全部用double来做就不用担心溢出了，只需把输出改为long即可。 
import java.io.*;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval;
            double[] height = new double[n];
            double l = 0, r = 0;
            for (int i = 0; i < n; i++) {
                in.nextToken();
                height[i] = in.nval;
                r = Math.max(r, height[i]);
            }
            double ans = r;
            while (l <= r) {
                double m = Math.floor((l + r) / 2);
                double power = m;
                boolean can = true;
                for (double i : height) {
                    power += power - i;
                    if (power < 0) {
                        can = false;
                        break;
                    }
                }
                if (can) {
                    ans = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            out.println(ans);

        }
        out.flush();
        out.close();
        br.close();
    }

}



编辑于 2024-01-20 21:51:21 回复(0)
Java
青春猪头少年不会没有offer头像 青春猪头少年不会没有offer
二分查找答案。 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long l = Integer.MAX_VALUE, r = Integer.MIN_VALUE;
        int[] h = new int[n];
        for (int i = 0; i < n; ++i) {
            h[i] = in.nextInt();
            if (h[i] < l) l = h[i];
            if (h[i] > r) r = h[i];
        }
        while (l < r) {
            long mid = l + r >> 1;
            if (check(mid, h)) r = mid;
            else l = mid + 1;
        }
        System.out.println(l);
    }

    public static boolean check(long e, int[] h) {
        int mx = Arrays.stream(h).max().getAsInt();
        for (int hh: h) {
            e += e - hh;
            e = Math.min(e, mx);
            if (e < 0) return false;
        }
        return true;
    }
}


发表于 2023-12-21 10:34:26 回复(0)
Java
tornado123头像 tornado123
如果是H(k+1) > E ，假设跳跃后为E2，有 E2 = E - (H(k+1) - E) = 2E - H(K+1);
如果是H(k+1) <= E，假设跳跃后为E2，有 E2 = E + (E - H(k+1)) = 2E - H(K+1);
无论哪种情况，最终都有 E2 = 2E - H(K+1)； -> E = (E2 + H(k+1) + 1)/2 -> 加一是为了向上取整。
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] h = new int[n+1];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }
        // 假设最后的能量值为0，这样子才能得到最少单位的初始能量
        int result = 0;
        for(int i = n - 1; i >= 0; i--) {
            result = (result + h[i] + 1) / 2;
        }
        System.out.println(result);
    }
}
发表于 2021-02-23 19:54:51 回复(0)
Java
hhhhh.头像 hhhhh.
倒推 
import java.util.Scanner;
public class Main{
public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    int n;
    n = scanner.nextInt();
    int[] shu = new int[n + 1];
    shu[0] = 0;

    for(int i = 1;i < n + 1;i++){
        shu[i] = scanner.nextInt();
    }
    int e = 0;
    for(int i = n ;i >= 1;i--){
        if((e + shu[i]) % 2 != 0){
           e = (e + shu[i]) / 2 + 1; 
        }
        else
        e = (e + shu[i]) / 2;
        
    }
    System.out.println(e);
}
}


发表于 2020-07-31 23:19:29 回复(1)
Java
awefag头像 awefag 
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        //存储的时候就倒着存储，这里采用的就是评论区里面大佬的思路
        //只不过是用java语言编写出来的版本
        //假设跳跃前能力为e,要跳的高度为H，那么跳跃后的能量就是2e-H，
        //那么跳跃后的能量加上高度就是跳跃前的两倍，然后从后往前逆推。
        //注意只需要设置最终的初始值为0即可，然后向上取整，使用到了Math.round()函数
        for(int i = n-1;i>=0;i--){
            a[i]= in.nextInt();
        }
        System.out.println(minEnergy(a));
        
    }
    public static int minEnergy(int[] a){
        int e = 0;
        for(int i = 0;i<a.length;i++){
            e =(int)Math.round((e+a[i])/2.0);
        }
        return e;
    }
}

发表于 2020-06-23 14:25:37 回复(0)
Java
何止hz头像 何止hz
二分搜索 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;

/**
 * @Date: 2020-05-06 22:35
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.valueOf(br.readLine());
        int h[] = new int[N];
        int r = 0;
        String[] s = br.readLine().split(" ");
        for (int i = 0; i < N; i++){
            h[i] = Integer.valueOf(s[i]);
            if (h[i] > r) r = h[i];
        }
        if (r ==0){
            System.out.println(0);
            return;
        }
        int l = 1;
        BigDecimal mid;
        while (l <= r){
            mid = new BigDecimal((l + r) >> 1);
            if (canReach(h, mid))
                r = mid.intValue() - 1;
            else
                l = mid.intValue() + 1;
        }
        System.out.println(l);
    }

    private static boolean canReach(int[] h, BigDecimal mid) {
        for (int i = 0; i < h.length; i++){
            mid = mid.add(mid.subtract(new BigDecimal(h[i])));
            if (mid.compareTo(new BigDecimal(0)) < 0)
                return false;
        }
        return true;
    }
}


发表于 2020-05-06 23:10:21 回复(0)
Java
1+½+¼+⅛+...头像 1+½+¼+⅛+... 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int[] H = new int[N+1];
        H[0] = 0;
        for(int i = 1; i < N+1; i++) {
        	H[i] = input.nextInt();
        }
        input.close();
        System.out.println(Solution(N, H));
    }
    
    public static int Solution(int N, int[] H) {
		int[] E = new int[N+1];
		E[N] = 0;
		for(int i = N; i > 0; i--) {
			E[i-1] = (H[i] + E[i] + 1) / 2;
		}
    	return E[0];    	
    }
    
}

编辑于 2019-09-06 14:25:25 回复(0)
Java
每文42头像 每文42 

	





	import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n;
        int ret=0;
        n = cin.nextInt();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = cin.nextInt();
        }
        int e = 0;
        for (int i = n-1; i >=0 ; i--) {
            e = (e+ h[i]) / 2 + (e+h[i])%2;
        }
        System.out.println(e);
    }
}
逆推即可
编辑于 2019-08-02 17:53:37 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 算法工程师 测试工程师 PHP工程师 字节跳动 2019 查找 Java工程师
上传者：小小
难度：
8条回答 22302浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号