二分法求机器人跳跃问题

简介: 二分法求机器人跳跃问题

机器人正在玩一个古老的基于 DOS 的游戏。


游戏中有 N+1 座建筑——从 0 到 N 编号,从左到右排列。


编号为 0 的建筑高度为 0 个单位,编号为 i 的建筑高度为 H(i) 个单位。


起初,机器人在编号为 0 的建筑处。


每一步,它跳到下一个(右边)建筑。


假设机器人在第 k 个建筑,且它现在的能量值是 E,下一步它将跳到第 k+1 个建筑。


如果 H(k+1)>E,那么机器人就失去 H(k+1)−E的能量值,否则它将得到 E−H(k+1)的能量值。


游戏目标是到达第 N 个建筑,在这个过程中能量值不能为负数个单位。


现在的问题是机器人至少以多少能量值开始游戏,才可以保证成功完成游戏?


输入格式

第一行输入整数 N

第二行是 N 个空格分隔的整数,H(1),H(2),…,H(N)代表建筑物的高度。


输出格式

输出一个整数,表示所需的最少单位的初始能量值上取整后的结果。

数据范围

1≤N,H(i)≤100000

输入样例1:

5
3 4 3 2 4

输出样例1:

4

输入样例2:

3
4 4 4


输入样例3:

3
1 6 4

输出样例3:

3

#include<iostream>
#include<cstdio>
using namespace std;
int h[100010], n;
int check(int e)
{
    int i = 0;
    for (i = 0; i < n; i++)
    {
        e = 2 * e - h[i];
        if (e >= 100000) return 1;
        if (e < 0) return 0;
    }
    return 1;
}
int main()
{
    cin >> n;
    int i = 0;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &h[i]);
    }
    int l = 0, r = 100000;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}
目录
相关文章
|
算法 机器人 C语言
【二分查找】分巧克力、机器人跳跃、数的范围
开始准备蓝桥杯啦!这是计划的一部分,每天都会更新一个专题的内容,内容参考自acwing蓝桥杯辅导课,有兴趣的uu们也可以自行观看
107 0
|
5月前
|
算法 机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
|
机器人
(二分)730. 机器人跳跃问题
(二分)730. 机器人跳跃问题
72 0
|
6月前
|
传感器 人工智能 监控
智能耕耘机器人
智能耕耘机器人
124 3
|
19天前
|
人工智能 搜索推荐 机器人
挑战未来职场:亲手打造你的AI面试官——基于Agents的模拟面试机器人究竟有多智能?
【10月更文挑战第7天】基于Agent技术,本项目构建了一个AI模拟面试机器人,旨在帮助求职者提升面试表现。通过Python、LangChain和Hugging Face的transformers库,实现了自动提问、即时反馈等功能,提供灵活、个性化的模拟面试体验。相比传统方法,AI模拟面试机器人不受时间和地点限制,能够实时提供反馈,帮助求职者更好地准备面试。
25 2
|
3月前
|
人工智能 算法 机器人
机器人版的斯坦福小镇来了,专为具身智能研究打造
【8月更文挑战第12天】《GRUtopia:城市级具身智能仿真平台》新论文发布,介绍了一款由上海AI实验室主导的大规模3D城市模拟环境——GRUtopia。此平台包含十万级互动场景与大型语言模型驱动的NPC系统,旨在解决具身智能研究中的数据稀缺问题并提供全面的评估工具,为机器人技术的进步搭建重要桥梁。https://arxiv.org/pdf/2407.10943
203 60
|
6月前
|
自然语言处理 机器人 Go
【飞书ChatGPT机器人】飞书接入ChatGPT,打造智能问答助手
【飞书ChatGPT机器人】飞书接入ChatGPT,打造智能问答助手
337 0

热门文章

最新文章