首页 > 试题广场 >

机器人跳跃问题

[编程题]机器人跳跃问题

热度指数：16968 时间限制：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

输出

示例2

输入

3
4 4 4

输出

示例3

输入

3
1 6 4

输出

备注:

数据约束：
1 <= N <= 10^5
1 <= H(i) <= 10^5

算法知识视频讲解

白伟仝

发表于 2020-05-09 17:53:39

最简解法： import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = 展开全文

laglangyue

发表于 2020-06-11 16:46:42

仔细读题目，e(k)+e(k)-H(k+1)=e(k+1)e(k)=(ek+1)+H(k+1))/2，注意这是临界条件，要用浮点数,完了向上取整。 import java.util.Scanner; public class Main { public static void main(St 展开全文

TonyBryant

发表于 2024-04-10 11:03:24

机器人跳跃问题题目分析： 1）机器人有一定的能量，要想跳过前方的所有障碍，所需能量的最小值 2）能找到一种 (正/负)相关的相关关系： ==》机器人所固有的能量越高，越能越过前方障碍 3）固有能量和能否越过障碍之间的关系的证明： eg: 机器人名字(能量)、柱高：value 两个机器人：展开全文

幕月志

发表于 2024-03-31 20:11:47

个人思路:二分答案算法该题具有单调性如所剩能量以及跳入下一个建筑的能量比较故可以采用二分算法进行解决 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=200050; ll 展开全文

SROMEI

发表于 2019-09-19 17:52:54

#include<bits/stdc++.h> using namespace std; int main(){ //简单逆推 int N = 0; while(cin >> N){ vector<int> en_li 展开全文

信仰_lee

发表于 2020-03-15 15:07:03

主要的思路是设到达最后一个时，能量消耗已经为0，接着依次逆序处理。由于中途存在向上取整的问题，所以计算出的最少能量在正序推时最后的能量不一定为0. #include<iostream> #include<iomanip> #include<vector> #inc 展开全文

ohJune

发表于 2023-03-06 22:29:27

注意E在每一层的值不一定相同，定义在k个建筑时，能量为Ek，可依次递推出等式 E1 = 2E0 - H1 ≥ 0 E2 = 2E1 - H2 = 4E0 - 2H1 - H2 ≥ 0 ··· Ek = 2Ek-1 - Hk ≥ 0 每个Ek值均大于0，每个等式均可以得到关于E0的一个下限，取下限的最展开全文

17c89

发表于 2023-12-21 12:31:02

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while 展开全文

大厂算法岗必拿下

发表于 2021-09-20 05:03:18

注意最后取天花板 #include<bits/stdc++.h> using namespace std; int main(){ int N,x; cin>>N; vector<int> v; for(int i =0; 展开全文

小牛冲冲冲jiang

发表于 2021-09-20 07:28:24

数学归纳 import java.util.Scanner; import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scan 展开全文

问题信息

C++工程师 iOS工程师安卓工程师运维工程师算法工程师测试工程师 PHP工程师字节跳动 2019 查找 Java工程师

上传者：小小

难度：

85条回答 346收藏 22248浏览

通过挑战的用户

查看代码

牛客57228...

2023-03-10 15:15:04
牛客23066...

2023-03-09 22:14:46
z84112938

2023-02-13 20:27:35
沉溺🌂

2023-02-13 19:48:53
Mudanyuan

2023-02-12 21:58:57

机器人跳跃问题

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题