AcWing730 机器人跳跃问题

这篇具有很好参考价值的文章主要介绍了AcWing730 机器人跳跃问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

机器人正在玩一个古老的基于 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) ≤ 105,

输入样例1:
5
3 4 3 2 4
输出样例1:
4
输入样例2:
3
4 4 4
输出样例2:
4
输入样例3:
3
1 6 4
输出样例3:
3
  • 分析题目
    暂设机器人当前能量是E
    机器人在跳跃时有两种情况:
    1.E < H(k + 1)
    E = E - ( H(k + 1) - E ) = 2E - H(k + 1);
    2.E >= H(k + 1)
    E = E + ( E - H(k + 1) ) = 2E - H(k + 1);
    可见无论哪种情况,机器人跳跃后的能量都是一样的,不必分情况

    题目让求能量的最小值 min,故当能量大于min时都符合题意,所以可以将能量区间分成两段,大于等于min和小于min。就可用二分法来求解

  • 代码如下文章来源地址https://www.toymoban.com/news/detail-822627.html

    • 小优化:
      当机器人跳跃到某一建筑的能量大于maxh时,就可以直接判断是符合条件的情况
      AcWing730 机器人跳跃问题,算法
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
const int N = 100005;
int maxh = 0, h[N], n, mid;
int check(int mid) {
  for (int i = 1; i <= n; i ++) {
  	if ((mid * 2 - h[i]) < 0) {
  		return 0;
  	}
  	if (mid > maxh) {
  		return 1;
  	}
  	mid = mid * 2 - h[i];
  }
  return 1;
}


int main () {
  cin >> n;
  //求建筑的最大高度
  for (int i = 1; i <= n; i ++) {
  	cin >> h[i];
  	maxh = max(h[i], maxh);
  }
  // 二分能量区间,看mid是否满足要求
  int l = 1, r = 100000;
  while (l < r) {
  	mid = (l + r) / 2;
  	if (check(mid)) {
  		r = mid;
  	} else
  		l = mid + 1;
  }
  cout << l;
  return 0;
}

到了这里,关于AcWing730 机器人跳跃问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 基于Dijkstra算法的机器人编队路径规划问题

    基于Dijkstra算法的机器人编队路径规划问题 路径规划是机器人领域中的一个重要问题,它涉及确定从起点到目标点的最佳路径。Dijkstra算法是一种经典的图算法,用于解决最短路径问题。在本文中,我们将介绍如何使用Dijkstra算法来实现机器人编队的路径规划,并提供相应的

    2024年02月08日
    浏览(48)
  • 基于遗传算法求解机器人栅格地图路径规划问题matlab仿真

     ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进, 代码获取、论文复现及科研仿真合作可私信。 🍎个人主页:Matlab科研工作室 🍊个人信条:格物致知。 更多Matlab完整代码及仿真定制内容点击👇 智能优化算法       神经网络预测       雷达通信    

    2024年01月22日
    浏览(57)
  • 【路径规划matlab代码】基于遗传算法求解机器人栅格地图路径规划问题

     ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进, 代码获取、论文复现及科研仿真合作可私信。 🍎个人主页:Matlab科研工作室 🍊个人信条:格物致知。 更多Matlab完整代码及仿真定制内容点击👇 智能优化算法       神经网络预测       雷达通信    

    2024年03月08日
    浏览(69)
  • 【路径规划】基于遗传算法求解机器人栅格地图路径规划问题matlab代码

     ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进, 代码获取、论文复现及科研仿真合作可私信。 🍎个人主页:Matlab科研工作室 🍊个人信条:格物致知。 更多Matlab完整代码及仿真定制内容点击👇 智能优化算法       神经网络预测       雷达通信    

    2024年01月24日
    浏览(64)
  • 宽度有限搜索BFS搜索数及B3625 迷宫寻路 P1451 求细胞数量 B3626 跳跃机器人

    题目描述 机器猫被困在一个矩形迷宫里。 迷宫可以视为一个 n×m 矩阵,每个位置要么是空地,要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。 机器猫初始时位于 (1,1) 的位置,问能否走到 (n,m) 位置。 输入格式 第一行,两个正整数 n,m。 接下来 n 行,输

    2024年02月13日
    浏览(39)
  • 中科院自动化所:基于关系图深度强化学习的机器人多目标包围问题新算法

    摘要:中科院自动化所蒲志强教授团队,提出一种基于关系图的深度强化学习方法,应用于多目标避碰包围问题(MECA),使用NOKOV度量动作捕捉系统获取多机器人位置信息,验证了方法的有效性和适应性。研究成果在2022年ICRA大会发表。   在多机器人系统的研究领域中,包围控

    2024年01月16日
    浏览(40)
  • 机器人控制算法——移动机器人横向控制最优控制LQR算法

    1.Introduction LQR (外文名linear quadratic regulator)即线性二次型调节器,LQR可得到状态线性反馈的最优控制规律,易于构成闭环最优控制。LQR最优控制利用廉价成本可以使原系统达到较好的性能指标(事实也可以对不稳定的系统进行整定) ,而且方法简单便于实现 ,同时利用 Matlab 强

    2024年02月04日
    浏览(47)
  • 扫地机器人(二分算法+贪心算法)

    1.  if(robot[i]-len=sweep)这个代码的意思是——如果机器人向左移动len个长度后,比现在sweep的位置(现在已经覆盖的范围)还要靠左,就是覆盖连续不起来,呢么这个len就是有问题的,退出函数,再继续循环。 2.  显然当每个机器人清扫的范围相同时,所用时间最小,所以这时

    2024年01月20日
    浏览(44)
  • 基于C#的机器人仿真平台和机器人运动学算法实现

    一、平台搭建 1.利用wpf自带的库进行机器人各关节导入 相关代码段: 导入效果如图: 效果视频: 2.通过正运动学显示机器人当前位置信息 拖动机器人并且实时改变其位置信息: xaml代码部分: 算法部分:  3.功能实现(在X/Y/Z轴上设置一个移动距离,然后机器人自动移动该

    2024年02月16日
    浏览(53)
  • 你知道机器人奇点吗?机器人奇点问题应该如何解决?

    原创/文 BFT机器人   “机器人奇点”——一个让机器人厂商和用户听到都闻风丧胆的词,一旦碰上,轻则重新编程调试,重则要和你的机器人say goodbye了。 提及“奇点“二字,你可能会立刻联想到黑洞。因为在物理学、宇宙学中,“奇点”也被称为时空奇点或引力奇点,它是

    2024年02月13日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包