二分法求机器人跳跃问题

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

机器人正在玩一个古老的基于 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们也可以自行观看
108 0
|
5月前
|
算法 机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
|
机器人
(二分)730. 机器人跳跃问题
(二分)730. 机器人跳跃问题
75 0
|
6月前
|
传感器 人工智能 监控
智能耕耘机器人
智能耕耘机器人
136 3
|
7天前
|
机器学习/深度学习 传感器 算法
智能机器人在工业自动化中的应用与前景###
本文探讨了智能机器人在工业自动化领域的最新应用,包括其在制造业中的集成、操作灵活性和成本效益等方面的优势。通过分析当前技术趋势和案例研究,预测了智能机器人未来的发展方向及其对工业生产模式的潜在影响。 ###
38 9
|
4天前
|
机器人 人机交互 语音技术
智能电销机器人源码部署安装好后怎么运行
销售打电销,其中90%电销都是无效的,都是不接,不要等被浪费了这些的精力,都属于忙于筛选意向客户,大量的人工时间都耗费在此了。那么,有这种新型的科技产品,能为你替代这些基本的工作,能为你提升10倍的电销效果。人们都在关心智能语音客服机器人如何高效率工作的问题,今天就为大家简单的介绍下:1、智能筛选系统:电销机器人目前已经达到一个真人式的专家级的销售沟通水平,可以跟客户沟通,筛选意向,记录语音和文字通话记录,快速帮助电销企业筛选意向客户,大大的节约了筛选时间成本和人工成本。2、高速运转:在工作效率上,人工电销员,肯定跟不上智能语音机器人,机器人自动拨出电话,跟客户交谈。电话机
75 0
|
1月前
|
人工智能 搜索推荐 机器人
挑战未来职场:亲手打造你的AI面试官——基于Agents的模拟面试机器人究竟有多智能?
【10月更文挑战第7天】基于Agent技术,本项目构建了一个AI模拟面试机器人,旨在帮助求职者提升面试表现。通过Python、LangChain和Hugging Face的transformers库,实现了自动提问、即时反馈等功能,提供灵活、个性化的模拟面试体验。相比传统方法,AI模拟面试机器人不受时间和地点限制,能够实时提供反馈,帮助求职者更好地准备面试。
53 2

热门文章

最新文章