首页 > 试题广场 > 机器人跳跃问题
[编程题]机器人跳跃问题
  • 热度指数:11603 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0N编号,从左到右排列。编号为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
import math

n = int(input())
H = [int(i) for i in input().split()]
E0 = 0
for i in range(n):
    E0 += H[i] / 2**(i+1)
print(math.ceil(E0))
由题干描述可以得出:
进而归纳得出:
令所有的,则需满足:
求得:
编辑于 2019-08-08 17:03:05 回复(3)
从后往前逆推
#include<iostream>
#include<vector>
 #include<cmath>
 using namespace std;
 int main(){
 int N;
 int ans = 0;
 cin >> N;
 vector<int>D(N,0);
 for(int i = 0;i<N;i++)
 cin >>D[i];
 for(int j=N-1;j>=0;j--){
 ans = ceil((D[j]+ans)/2.0);//注意c++中除法整数/整数为0,ceil向上取整要整数/float类型
 }
 cout<<ans<<endl;
 return 0;
 }

编辑于 2019-07-24 16:20:34 回复(9)
input()
arr = list(map(int, input().split(' ')))
# 假设跳跃前能力为E,要跳的高度为H,那么跳跃后的能量就是2E-H,
# 那么跳跃后的能量加上高度就是跳跃前的两倍,然后从后往前逆推。
E = 0    # 跳到最后一步的能力值设为0
arr.reverse()
for H in arr:
    E = (E + H + 1) >> 1
print(E)

发表于 2019-08-18 15:45:57 回复(0)
#include <vector>
#include <iostream>
#include <math.h>

class Solution { 
public:
  static void solve(const std::vector<int>& data) { 
    
    // need:到达终点的所需要最小的能量
    int need=0; 

    /**
     * @brief: 到达终点能量为0时,开始所需能量最小。
     *         从终点开始倒推理,推理出前一步所需的能量。
     *         一直递推到起点
     * 
     * 为什么需要 ceil(...)? 
     * 
     * 因为会出现 (*iter + need) 为奇数,如果不向上取整,就会少1,最后到终点时不是0,而是-1
     * 
     * 比如,输入如下:
     * 
     *  3
     *  3 2 4
     * 
     *  正确结果是3,但是实际上输出2,就是因为没有向上取整。
    */
    for(auto iter=data.rbegin(); iter != data.rend(); ++iter) { 
      need = ::ceil(static_cast<float>((*iter + need)) / 2); // 向上取整
    }

    std::cout<<need<<std::endl;;
  }
};

int main(int argc, char const *argv[]) {

  int N=0;
  std::cin>>N;
  std::vector<int> data(N);

  for(int i=0; i < N; ++i) { 
    std::cin>>data[i];
  }

  Solution::solve(data);

  return 0;
}
对一个前排大佬的代码的一点注释。牛客网的markdown真垃圾,本想发在评论里,但是没有格式了。


发表于 2020-06-03 15:49:15 回复(0)
二分法即可,只需注意机器人在什么条件下一定会到达终点即可。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
        public static void main(String[] args) {
                Scanner scanner = new Scanner(System.in);
                int n = scanner.nextInt();
                scanner.nextLine();
                int[] a =new int[n];
                long sum=0;
                for(int i = 0 ;i<n;i++){
                        a[i] = scanner.nextInt();
                        sum = Math.max(sum,a[i]);
                }
                long low = 0;
                long high = sum;
                long mid = 0;
                while (low<=high){
                        mid = (low+high)/2;
                        if(check(a,mid)){
                                high = mid-1;
                        }else
                                low = mid+1;
                }
                System.out.println(low);

        }
        public static boolean check(int[] a,long e){
                int maxm=0;
                for(int i = 0;i<a.length;i++){
                        maxm = Math.max(maxm,a[i]);
                }
                for(int i = 0;i<a.length;i++){
                        if(e>maxm)
                                return true;
                        if(e<a[i]){
                                e -=a[i]-e;
                        }else{
                                e+=e-a[i];
                        }
                        if(e<0)
                                return false;
                }
                return true;
        }
}

发表于 2021-03-03 16:00:50 回复(0)
如果是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)
逆推 当前在第k个建筑 设x为能通过第k个建筑的能量值  x+x-h(k-1)  =  当前建筑最低能通过的能量值
#include<math.h>
int main(){
    int i,n;
    double a[1000],enegy=0,temp;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%lf",&a[i]);
    }
    temp=0;
    for(i=n;i>=1;i--){
        enegy= ceil((a[i-1]+temp)/2.0);
        temp=enegy;
    }
    printf("%.0f",enegy);
    

发表于 2020-03-15 17:39:52 回复(0)
#简单二分法
#最少要多少能量能跳完整个路径
n = int(input())
E = [int(x) for x in input().strip().split()]
low = 0
high = sum(E)
while low < high:
    mid = (low + high) // 2
    #从第1个开始跳
    flag = 0
    EE = mid
    for i in range(n):
        if E[i] > EE:
            EE -= E[i] - EE
        else:
            EE += EE - E[i]
        if EE < 0:
            flag = 1
            break
    #此能量够用
    if flag == 0:
        high = mid
    else:
        low = mid + 1
print(low)

发表于 2019-08-11 12:30:25 回复(0)
依题意容易得到k位置和k+1位置的能量递推式,假设到达终点的时候能量刚好用尽,我们就可以利用递推式倒推得到起点0处的能量值。
from math import ceil

n = int(input())
H = list(map(int, input().split()))
E = 0      # 最后到达终点能量已经耗尽
# 倒推得到0位置处的初始能量
for i in range(n - 1, -1, -1):
    # E[k+1]=2E[k]-H[k+1] => E[k]=(H[k+1]+E[k+1])/2
    E = ceil((H[i] + E)/2)
print(E)


发表于 2021-02-01 17:39:59 回复(0)
初始能量E为0,依次累加求最优解
n = int(input())
li = [int(x) for x in input().split()]
E = 0
while 1:
    ee = E
    for i in li:
        ee = 2 * ee - i
        if ee < 0:
            break
    else:
        print(E)
        break
    E += 1


发表于 2020-09-19 00:23:52 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,e=0;
    cin>>n;
    int h[n];
    for(int i=0;i<n;i++)
        cin>>h[i];
    for(int i=n-1;i>=0;i--)
        e = (e+h[i]+1)>>1;
    cout<<e<<endl;
    return 0;
}

发表于 2019-09-13 03:17:52 回复(0)
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int main() {
    int N;
    cin >> N;
    vector<long double> hs(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> hs[i];
    }
    long double res = 0;
    for (int i = N; i >= 1; --i) {
        res = (res + hs[i]) / 2;
    }
    cout << ceil(res) << endl;
    return 0;
}


发表于 2019-08-24 14:44:33 回复(0)

二分

n = int(input())
high = list(map(int, input().split()))

left, right = 0, max(high)

def fun(power):
    for i in range(n):
        if power > high[i]:
            power += power - high[i]
        else:
            power -= high[i] - power
        if power < 0:
            return False
    return True

while left < right:
    mid = (left + right) >> 1
    if fun(mid):
        right = mid
    else:
        left = mid + 1

print(left)
发表于 2019-05-28 20:49:43 回复(3)
我觉得有问题吧,首先把最后一个建筑能量设为0就是错误的。假设有五个建筑,分别是1,10,2,5,4.那他至少开局要有10的能量才能到终点啊。如果按照代码来讲,很多代码结果是4,开局四点能量顶多到第一个建筑。
发表于 2019-09-05 14:10:05 回复(5)
小学数学知识,逆推法(终点处能量最小为0)
import math n = int(input()) h = [0]+list(map(int, input().split())) E = [0]*(n+1) for i in range(n-1,-1,-1):  E[i] = (E[i+1]+h[i+1])*0.5 print(math.ceil(E[0]))


编辑于 2019-06-27 06:02:14 回复(0)
此题用java来解决有点坑,从题面上来看简单的使用二分法就能得出答案,但是在运行的时候
总是只能ac百分之几,同样的代码用python可以很简单的通过,找了半天没有找到原因。后来debug才发现,
在能量够大的情况下一直累加导致long型数据超出界限。只要加上一句
if(num > 500000){return true;},即可。因为当能量达到500000时,即便后面不可能再使能量减少,此时必定符合要求。
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        int left = 1;int right = 100000;
        Main main = new Main();

        while(right > left +1){
            int mid = (right + left) / 2;

            if(main.isPass((long)mid,a)){
                right = mid;
            }else{
                left = mid;
            }
        }
        if(main.isPass(left,a)){
            System.out.println(left);
        }else {
            System.out.println(right);
        }

    }
    public boolean isPass(long num,long[] a){
        for(int i=0;i<a.length;i++){
            if(num <= a[i]){
                num -= a[i] - num;
            }else{
                num += num -a[i];
            }
            if(num > 500000){
                return true;
            }
            if (num < 0){
                return false;
            }
        }
        return true;
    }
}

编辑于 2019-11-26 12:52:05 回复(6)

蒟蒻一眼看去是个单调的,就懒得推公式了,上来整了个二分答案

import java.util.Scanner;

public class Main {
    static int N;
    static int[] arr;
    static int arr_max = -1;

    public static boolean judge(long x){
        for(int i = 1;i <= N;i ++){
            if(arr[i] > x){
                x -= (arr[i] - x);
            } else {
                x += (x - arr[i]);
            }
            if(x < 0) return false;
            if(x > arr_max) return true;//若不记录最大值,能量会超过long的最大值
        }
        return true;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        arr = new int[N+5];
        for(int i = 1;i <= N;i++){
            arr[i] = scanner.nextInt();
            arr_max = Math.max(arr_max, arr[i]);
        }

        long l = 0, r = Integer.MAX_VALUE;
        long ans = Integer.MAX_VALUE;
        while(l <= r){//优雅的二分
            long mid = (l+r) / 2;
            if(judge(mid)){
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(ans);
        scanner.close();
    }
}
发表于 2021-04-23 21:20:23 回复(0)
import math

N = int(input())
H = [0] + [int(x) for x in input().split()]
E = [0] * (N + 1)
for i in range(N, -1, -1):
    E[i-1] = math.ceil((E[i] + H[i]) / 2)
print(E[0])
从后往前模拟,记得向上取整

发表于 2021-03-13 11:45:11 回复(0)
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); double res=0,divisor; int[] array=new int[n]; for(int i=0;i
发表于 2021-03-10 22:23:43 回复(0)
// 二分法 
/** 
    二分法找区间  如果 mid 可以找到就 缩小范围 知道循环结束
    判断等否找到 j这个指针到达了 n - 1 
    题目里面我确实没看出来哪里要求了要double精度的 
    个人觉得比较离谱
**/
import java.util.*;
public class Main{
    public double findEnergy(double[] buildings){
        double start = 0, end = Double.MAX_VALUE;
        while(start + 1 < end){
            double mid = start + (end - start) / 2;
            if(canJump(buildings, mid)){
                end = mid;
            }else{
                start = mid;
            }
        }
        if(canJump(buildings,start)){
            return start;
        }
        if(canJump(buildings, end)){
            return end;
        }
        return -1;
    }


    public boolean canJump(double[]buildings, double e){
        //System.out.println("entered");
        int n = buildings.length;
        int j = 0;
        while(j < n){
            double energyDiff = e - buildings[j];
            if (energyDiff < 0) {
                if (e + energyDiff < 0) {
                    return false;
                }
            }
            e += energyDiff;
            j++;
        }
        //System.out.println(j);
        return j >= n - 1;
    }
    
    public static void main(String[] args){
        Main test = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double[] buildings = new double[n];
        for(int i = 0; i < n; i++){
            buildings[i] = sc.nextDouble();
            //System.out.println(buildings[i]);
        }
        System.out.println((int)Math.ceil(test.findEnergy(buildings)));
    }
}

发表于 2021-03-07 10:55:49 回复(0)