当前位置: 首页 > news >正文

(二分)730. 机器人跳跃问题

目录

题目链接

一些话

        切入点 

流程

套路

ac代码


题目链接

AcWing 730. 机器人跳跃问题 - AcWing


一些话

// 向上取整 mid的表示要写成l + r + 1 >> 1即可,向下取整 mid = l + r >> 1
// 这里我用了浮点二分,mid = (l + r) / 2,最后再手动写了个向上取整的句子,所以没有wa,可能是题目数据太弱。
// 已经申请了加强数据了


切入点 

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

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

机器人在满足条件的情况下能通过的建筑数量与初始能量值正相关,符合二分特性


流程

//二分check部分是个小模拟,按照模拟步骤写伪代码,然后等价替换

// 递推,枚举每一个台阶,然后对mid操作,每次操作后判断mid是否跳出了0~1e5的区间,小于0return false,大于0return true;
    // 枚举结束了后return true;

等价替换后的伪代码: 


// 写check函数伪代码(流程)的时候可以发现,不管mid和f[i]的大小关系如何,最终都是mid = 2 * mid - f[i];
// 因此写代码时就不用再分情况讨论,只要写一个mid = 2 * mid - f[i] 就可以了,然后还有一个剪枝操作,
// 因为f[i]max = 1e5,所以只要mid>1e5,直接return true就可以了

   

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

这个我是真无语了,一直纠结yxc代码哪里用了向上取整,其实这道题不用浮点二分的话得到的答案肯定是大于浮点二分的精确小数答案的,所以用整数二分本身就是一个向上取整了


套路

二分的取整

①向上取整 mid的表示要写成

        l + r + 1 >> 1即可,

②向下取整

        mid = l + r >> 1


ac代码

// 11:11 ~11:14读题
// ~24 ac
// 向上取整 mid的表示要写成l + r + 1 >> 1即可,向下取整 mid = l + r >> 1
// 这里我用了浮点二分,mid = (l + r) / 2,最后再手动写了个向上取整的句子,所以没有wa,可能是题目数据太弱。
// 已经申请了加强数据了//二分check部分是个小模拟,按照模拟步骤写伪代码,然后等价替换
// 写check函数伪代码(流程)的时候可以发现,不管mid和f[i]的大小关系如何,最终都是mid = 2 * mid - f[i];
// 因此写代码时就不用再分情况讨论,只要写一个mid = 2 * mid - f[i] 就可以了,然后还有一个剪枝操作,
// 因为f[i]max = 1e5,所以只要mid>1e5,直接return true就可以了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
double f[N],n,maxn;
bool check(double mid){// 递推,枚举每一个台阶,然后对mid操作,每次操作后判断mid是否跳出了0~1e5的区间,小于0return false,大于0return true;// 枚举结束了后return true;// 可推导出mid = 2 * mid - f[i];// for(int i = 1;i <= n;i++){if(mid >= f[i]) mid += mid - f[i];else mid -= (f[i] - mid);if(mid < 0) return false;}return true;
}
int main(){cin >> n;for(int i = 1;i <= n;i++) {scanf("%lf",&f[i]);maxn = max(f[i],maxn);}double l =  1,r = maxn;while(r - l > 1e-3){double mid = (l + r) / 2;if(check(mid)) r = mid;else l = mid;}if(int(l * 10) % 10) l += 1;cout << (int)l << endl;return 0;
}


我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草   ,又          ~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦! 字~数~啦!我草   ,又          ~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦! 字~数~啦!我草   ,又          ~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦! 字~数~啦!我草   ,又          ~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦! 字~数~啦!我草   ,又          ~在~水~字~数~啦!我草,又~在~水~字~数~啦!我草,又~在~水~字~数~啦! 

相关文章:

(二分)730. 机器人跳跃问题

目录 题目链接 一些话 切入点 流程 套路 ac代码 题目链接 AcWing 730. 机器人跳跃问题 - AcWing 一些话 // 向上取整 mid的表示要写成l r 1 >> 1即可&#xff0c;向下取整 mid l r >> 1 // 这里我用了浮点二分&#xff0c;mid (l r) / 2&#xff0c;最…...

vue3使用nextTick

发现nextTick必须放在修改一个响应式数据之后&#xff0c;才会在onUpdated之后被调用&#xff0c;如果nextTick是放在所有对响应式数据修改之前&#xff0c;则nextTick里面的回调函数会在onBeforeUpdate方法执行前就被调用了。可是nextTick必须等到onUpdated执行完成之后执行&a…...

传统图像处理之颜色特征

博主简介 博主是一名大二学生&#xff0c;主攻人工智能研究。感谢让我们在CSDN相遇&#xff0c;博主致力于在这里分享关于人工智能&#xff0c;c&#xff0c;Python&#xff0c;爬虫等方面知识的分享。 如果有需要的小伙伴可以关注博主&#xff0c;博主会继续更新的&#xff0c…...

GPS问题调试—MobileLog中有关GPS关键LOG的释义

GPS问题调试—MobileLog中有关GPS关键LOG的释义 [DESCRIPTION] 在mobile log中,有很多GPS相关的log出现在main log和kernel log、properties文件中,他们的意思是什么,通过这篇文档进行总结,以便在处理GPS 问题时,能够根据这些log快速的收敛问题。 [SOLUTION] 特别先提醒…...

【企业管理】你真的理解向下管理吗?

导读&#xff1a;拜读陈老师一篇文章《不会向下负责&#xff0c;你凭什么做管理者&#xff1f;》&#xff0c;引发不少共鸣&#xff0c;“很多管理者有一种错误的观念&#xff0c;认为管理是向下管理&#xff0c;向上负责。其实应该反过来&#xff0c;是向上管理&#xff0c;向…...

Centos7 硬盘挂载流程

1、添加硬盘到Linux&#xff0c;添加后重启系统2、查看添加的硬盘&#xff0c;lsblksdb 8:16020G 0disk3、分区fdisk /dev/sdbmnw其余默认&#xff0c;直接回车再次查看分区情况&#xff0c;lsblksdb1 8:17 0 20G 0 part4、格式化mkfs -t ext4 /dev/sdb15、挂载mkdir /home/new…...

认识vite_vue3 初始化项目到打包

从0到1创建vite_vue3的项目背景效果vite介绍&#xff08;对比和vuecli的区别&#xff09;使用npm创建vitevitevuie3创建安装antdesignvite自动按需引入&#xff08;vite亮点&#xff09;请求代理proxy打包背景 vue2在使用过程中对象的响应式不好用新增属性的使用$set才能实现效…...

【Go】cron时间格式

【Go】cron时间格式 Minutes&#xff1a;分钟&#xff0c;取值范围[0-59]&#xff0c;支持特殊字符* / , -&#xff1b;Hours&#xff1a;小时&#xff0c;取值范围[0-23]&#xff0c;支持特殊字符* / , -&#xff1b;Day of month&#xff1a;每月的第几天&#xff0c;取值范…...

leetcode 55. 跳跃游戏

给定一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1&#xff1a; 输入&#xff1a;nums [2,3,1,1,4] 输出&#xff1a;true 解释&#xff1a;可以先跳 1 …...

Linux:文件流指针 与 文件描述符

目录一、文件描述符二、文件流指针三、缓冲区之前讲解过了IO库函数和IO接口&#xff0c;库函数是对系统调用接口的封装&#xff0c;也就是说实际上在库函数内部是通过调用系统调用接口来完成最终功能的。 库函数通过文件流指针操作文件&#xff0c;系统调用接口通过文件描述符操…...

基于FPGA实现正弦插值算法

1、正弦插值的算法分析 1.1 信号在时域与频域的映射关系 在进行正弦算法分析之前&#xff0c;我们回顾一下《数字信号处理》课程中&#xff0c;对于信号在时域与频域之间的映射关系&#xff0c;如下图。 对于上图中的原始信号x(t)&#xff0c;使用ADC对信号进行采样&#xff0…...

JavaWeb_会话技术

文章目录会话跟踪技术的概述Cookie概念Cookie工作流程Cookie基本使用发送Cookie获取CookieCookie原理分析Cookie的使用细节Cookie的存活时间Cookie存储中文SessionSession的基本使用概念工作流程Session的基本使用Session的原理分析Session的使用细节Session的钝化与活化Sessio…...

Reactor响应式流的核心机制——背压机制

响应式流是什么&#xff1f; 响应式流旨在为无阻塞异步流处理提供一个标准。它旨在解决处理元素流的问题——如何将元素流从发布者传递到订阅者&#xff0c;而不需要发布者阻塞&#xff0c;或订阅者有无限制的缓冲区或丢弃。 响应式流模型存在两种基本的实现机制。一种就是传统…...

[数据结构]栈的深入学习-java实现

CSDN的各位uu们你们好,今天千泽带来了栈的深入学习,我们会简单的用代码实现一下栈, 接下来让我们一起进入栈的神奇小世界吧!0.速览文章一、栈的定义1. 栈的概念2. 栈的图解二、栈的模拟实现三.栈的经典使用场景-逆波兰表达式总结一、栈的定义 1. 栈的概念 栈&#xff1a;一种…...

网络编程基础

1 互联网的本质硬件设备有了操作系统&#xff0c;然后装上软件之后我们就能够正常使用了&#xff0c;然后也只能自己使用。像这样&#xff0c;每个人都拥有一台自己的机器&#xff0c;然而彼此孤立。如何才能和大家一起愉快的玩耍&#xff1f;什么是网络&#xff1f;简单来说&a…...

华为OD机试题 - 数列还原(JavaScript)| 机考必刷

更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解:数列还原题目输入输出示例一输入输出Code代码解析版权说明华为O…...

10-Oracle存储过程(创建,修改,使用及管理)

本章内容 1、我们为什么要用存储过程? 2、存储过程是如何定义和维护的? 3、我们如何调用存储过程? 4、存储过程中常用的复合数据处理方式及CTE 5、存储过程如何进行异常处理? 6、存储过程如何进行事务处理? 7、我们应如何优化存储过程? 1、我们为什么要用存储过程…...

创建线程的三种方法

文章目录1、创建一个类实现Runnable接口&#xff0c;并重写run方法。2、创建一个类继承Thread类&#xff0c;并重写run方法。3、实现Callable接口&#xff0c;重写call()方法&#xff0c;这种方式可以通过FutureTask获取任务执行的返回值。4、run()方法和start()方法有什么区别…...

第一章---Pytorch快速入门---第三节---pytorch中的数据操作和预处理

目录 1.高维数组 1.1 回归数据准备 1.2 分类数据准备 2. 图像数据 1.torchvision.datasets模块导入数据并预处理 2.从文件夹中导入数据并进行预处理 pytorch中torch.utils.data模块包含着一些常用的数据预处理的操作&#xff0c;主要用于数据的读取、切分、准备等。 常用…...

【代码随想录训练营】【Day38】第九章|动态规划|理论基础|509. 斐波那契数|70. 爬楼梯|746. 使用最小花费爬楼梯

理论基础 动态规划与贪心的区别并不是学习动态规划所必须了解的&#xff0c;所以并不重要。 想要了解动态规划算法题的特点&#xff0c;可以直接做下面三道入门简单题练练手感&#xff0c;找找感觉&#xff0c;很快就能体会到动态规划的解题思想。 总结成一句话就是&#xf…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

Linux安全加固:从攻防视角构建系统免疫

Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...

react-pdf(pdfjs-dist)如何兼容老浏览器(chrome 49)

之前都是使用react-pdf来渲染pdf文件&#xff0c;这次有个需求是要兼容xp环境&#xff0c;xp上chrome最高支持到49&#xff0c;虽然说iframe或者embed都可以实现预览pdf&#xff0c;但为了后续的定制化需求&#xff0c;还是需要使用js库来渲染。 chrome 49测试环境 能用的测试…...

WinUI3开发_使用mica效果

简介 Mica(云母)是Windows10/11上的一种现代化效果&#xff0c;是Windows10/11上所使用的Fluent Design(设计语言)里的一个效果&#xff0c;Windows10/11上所使用的Fluent Design皆旨在于打造一个人类、通用和真正感觉与 Windows 一样的设计。 WinUI3就是Windows10/11上的一个…...

NineData数据库DevOps功能全面支持百度智能云向量数据库 VectorDB,助力企业 AI 应用高效落地

NineData 的数据库 DevOps 解决方案已完成对百度智能云向量数据库 VectorDB 的全链路适配&#xff0c;成为国内首批提供 VectorDB 原生操作能力的服务商。此次合作聚焦 AI 开发核心场景&#xff0c;通过标准化 SQL 工作台与细粒度权限管控两大能力&#xff0c;助力企业安全高效…...