算法日记1:洛谷p2678跳石头(二分答案)
1、题目
二、题解:
2.1解题思路:
1.题目要求求出最小值最大,明显的二分答案题目,所以我们可以二分可以跳跃距离
int l=-1,r=L+1;
2.此时我们思考l=mid和r=mid的处理,当我们的check(mid)为true时候 表明我们此时的mid是符合要求的,
那么我们就要考虑是否可以变得更大呢?因此我们的二分答案可以这样写
int l=-1,r=L+1;while(l+1<r){int mid=(l+r)>>1;if(check(mid)) l=mid; //当check为true时,表示符合条件,我们就要考虑是否可以更大else r=mid;} if(check(r)) cout<<r<<'\n';else cout<<l<<'\n';
3.接下来,我们来处理check(mid)
函数
法一:好实现但是难想
首先我们定义一些变量来处理问题
int cnt=0; //计数器
int i=0,now=0; //i-->枚举每一个石头,now表示当前跳到了哪一个石头上
接下来,我们枚举每一个石头,
1.并且我们无论如何都会往下枚举,所以i++是永恒成立的
2.那么问题来了,我们如何实现把一个石头给踢掉的操作呢?2.1.答案是通过操作cnt和now,因为当需要踢掉这个石头的时候,一定需要+1的,所以cnt++;
但是我们此时不一定可以让now=i,因为我们可能会出现需要搬走连续的两个石头,所以只有当
a[i]-a[now]>mid,我们才会跳跃
代码解析
bool check(int mid) //检查此时这个距离是否可以达成
{int cnt=0; //计数器int i=0,now=0; //i-->枚举每一个石头,now表示当前跳到了哪一个石头上while(i<n+1) //枚举每一个石头{i++;if(a[i]-a[now]<mid) //表明此时的距离不满足要求{cnt++; //纯让次数加1,也就是当作把这块石头踢掉,因为我此时i++是必然会进行的,//但是我的now没有改变也就意味着这块石头我没有跳,遍历到了下一块石头。}else //表明此时距离已经>mid可以跳跃{now=i; //}}if(cnt<=m) return true;else return false;
}
法二(好想但是难实现):
首先我们定义一些变量来处理问题
int cnt=0; //计数器
int i=0,now=0; //i-->枚举每一个石头,now表示当前跳到了哪一个石头上
接下来,我们枚举每一个石头,
1.并且我们无论如何都会往下枚举,所以i++是永恒成立的
2.那么问题来了,我们如何实现把一个石头给踢掉的操作呢?2.1:在法一中,我们通过cnt的处理来抽象的实现跳跃这个操作
但是我们仍然可以用一个whle死循环来实现两个/两个以上的连续石头不符合条件的情况
我们把if
–>while
,这样,当出循环时,就一定使得此时的下一个石头的距离是合理的。
PS:注意此时需要防止i的遍历溢出!!!
代码如下😂:
bool check(int mid) //检查此时这个距离是否可以达成
{int cnt=0; //计数器int i=0,now=0; //i-->枚举每一个石头,now表示当前跳到了哪一个石头上while(i<n+1) //枚举每一个石头{i++;while(a[i]-a[now]<mid) //表明此时的距离不满足要求{cnt++;if(i<n+1) //还没遍历完成{i++; //防止都不满足溢出}else //表明此时i已经遍历完了n,那么就直接进行判断{if(cnt<=m) return true;else return false;}}now=i; //表示跳到这个石头上面}if(cnt<=m) return true;else return false;
}
三、完整代码解析
法一:
#include<iostream>
using namespace std;const int N=2e5;
int a[N];
int L,n,m;bool check(int mid) //检查此时这个距离是否可以达成
{int cnt=0; //计数器int i=0,now=0; //i-->枚举每一个石头,now表示当前跳到了哪一个石头上while(i<n+1) //枚举每一个石头{i++;if(a[i]-a[now]<mid) //表明此时的距离不满足要求{cnt++; //纯让次数加1,也就是当作把这块石头踢掉,因为我此时i++是必然会进行的,//但是我的now没有改变也就意味着这块石头我没有跳,遍历到了下一块石头。}else //表明此时距离已经>mid可以跳跃{now=i; //}}if(cnt<=m) return true; //(踢石头数<可以踢的数量) 满足条件else return false;
}int main()
{cin>>L>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}a[n+1]=L; //样例准备int l=-1,r=L+1;while(l+1<r){int mid=(l+r)>>1;if(check(mid)) l=mid;else r=mid;}if(check(r)) cout<<r<<'\n';else cout<<l<<'\n';return 0;
}
法二:
#include<iostream>
using namespace std;const int N=2e5;
int a[N];
int L,n,m;bool check(int mid) //检查此时这个距离是否可以达成
{int cnt=0; //计数器int i=0,now=0; //i-->枚举每一个石头,now表示当前跳到了哪一个石头上while(i<n+1) //枚举每一个石头{i++;while(a[i]-a[now]<mid) //表明此时的距离不满足要求{cnt++;if(i<n+1) //还没遍历完成{i++; //防止都不满足溢出}else //表明此时i已经遍历完了n,那么就直接进行判断{if(cnt<=m) return true;else return false;}}now=i; //表示跳到这个石头上面}if(cnt<=m) return true;else return false;
}int main()
{cin>>L>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}a[n+1]=L; //样例准备int l=-1,r=L+1;while(l+1<r){int mid=(l+r)>>1;if(check(mid)) l=mid;else r=mid;}if(check(r)) cout<<r<<'\n';else cout<<l<<'\n';return 0;
}
相关文章:
算法日记1:洛谷p2678跳石头(二分答案)
1、题目 二、题解: 2.1解题思路: 1.题目要求求出最小值最大,明显的二分答案题目,所以我们可以二分可以跳跃距离int l-1,rL1; 2.此时我们思考lmid和rmid的处理,当我们的check(mid)为true时候 表明我们此时的mid是符合要求的, 那么…...
PID控制器 (Proportional-Integral-Derivative Controller) 算法详解及案例分析
PID控制器 (Proportional-Integral-Derivative Controller) 算法详解及案例分析 目录 PID控制器 (Proportional-Integral-Derivative Controller) 算法详解及案例分析1. 引言2. PID控制器的基本概念2.1 PID控制器的定义2.2 PID控制器的核心思想2.3 PID控制器的应用领域 3. PID控…...
Vue中nextTick实现原理
源码实现思路(面试高分回答) 面试官问我 Vue 的 nextTick 原理是怎么实现的,我这样回答: 在调用 this.$nextTick(cb) 之前: 存在一个 callbacks 数组,用于存放所有的 cb 回调函数。存在一个 flushCallbac…...
【MATLAB】subplot如何增加title
在 Matlab 中,使用 subplot 函数将图形窗口划分为多个子图,并使用 title 函数为每个子图添加标题。以下是一个示例: matlab % 生成示例数据 x 0:0.1:10; y1 sin(x); y2 cos(x); % 创建一个 2 行 1 列的子图布局,并选…...
vue3+ts的<img :src=““ >写法
vue3ts的<img :src"" >写法<img :src"datasetImage" alt"数据分布示意图" /><script setup lang"ts">const datasetImage ref();datasetImage.value new URL(../../../assets/images/login-background.jpg, impo…...
Vue+Echarts+百度地图 实现 路径规划
实现功能: 通过选择 相关调拨,系统自动规划 路径,并且以地图的形式呈现最佳路径 技术难点: 1. vue 结合使用 echarts 2.echarts 在 vue嵌入百度地图,并且做出路径 曲线 最终结果:...
uniapp 小程序 textarea 层级穿透,聚焦光标位置错误怎么办?
前言 在开发微信小程序时,使用 textarea 组件可能会遇到一些棘手的问题。最近我在使用 uniapp 开发微信小程序时,就遇到了两个非常令人头疼的问题: 层级穿透:由于 textarea 是原生组件,任何元素都无法遮盖住它。当其…...
IGP协议的双点双向注入(路由引入)
一、拓扑环境 二、单向注入 以上拓扑为例,单点注入存在路由回包问题 在AR5上注入直连路由 55.5.5.5 需求:AR1上的10.1.1.1 需访问AR5上的55.5.5.5 1、在AR2和AR3上查看注入的55.5.5.5的路由信息 2、现在边界设备以学习到目的网段的路由信息࿰…...
【React】新建React项目
目录 create-react-app基础运用React核心依赖React 核心思想:数据驱动React 采用 MVC体系package.jsonindex.html好书推荐 官方提供了快速构建React 项目的脚手架: create-react-app ,目前使用它安装默认是19版本,我们这里降为18…...
“AI 自动化效能评估系统:开启企业高效发展新征程
在当今数字化飞速发展的时代,企业面临着日益激烈的市场竞争,如何提升效率、降低成本成为了企业生存与发展的关键。AI 自动化效能评估系统应运而生,它如同一把智能钥匙,为企业开启了高效发展的新征程。 AI 自动化效能评估系统&…...
免 root 开启 Pixel 手机 VoLTE 功能
部分运营商需要开启 VoLTE 功能才可以正常通话和接收短信,但是默认情况下,Pixel 是无法开启的,需要我们手动开启一下。经过网友的确认,这种方法还适用于荣耀 MAGIC 等其他品牌的手机。 具体流程如下: 1.打开开发者选…...
华为2024嵌入式研发面试题
01 你认为最好的排序算法是什么? 在实际的编程中,最好的排序算法要根据实际需求和数据规模来选择,因为每种排序算法都有其优势和劣势。以下是一些常见排序算法及其优缺点: 冒泡排序 冒泡排序是一种简单直观的排序算法࿰…...
Android Room 报错:too many SQL variables (code 1 SQLITE_ERROR) 原因及解决方法
报错信息: android.database.sqlite.SQLiteException: too many SQL variables (code 1 SQLITE_ERROR): while compiling: SELECT * FROM points WHERE id IN (?,?,?,...,?,?,?)SQLiteException: too many SQL variables 通常是由于一次查询或插入的 SQL 语句…...
PHP 字符串
PHP 字符串 引言 在 PHP 中,字符串是一种非常基础且重要的数据类型。字符串可以包含字母、数字、标点符号以及特殊字符。PHP 提供了丰富的字符串函数,使得字符串操作变得简单而高效。本文将详细介绍 PHP 中字符串的常用操作,包括字符串的创…...
Android15源码编译问题处理
最近想在Raspberry Pi5上面运行自己编译的Android15镜像,参考如下链接来处理: GitHub - raspberry-vanilla/android_local_manifest GitHub - raspberry-vanilla/android_kernel_manifest 代码同步完后,编译就出问题了,总是提示: FAILED: analyzing Android.bp files and…...
Transformer架构和Transformers 库和Hugging Face
Transformer架构 和 Hugging Face 之间的关系非常紧密,Hugging Face 是推动 Transformer 架构普及和应用的重要力量。以下是两者的关系及其具体联系: 1. Transformer 架构 背景: Transformer 是由 Google 在 2017 年提出的革命性架构,基于自…...
【机器学习 | 数据挖掘】离群点检测
【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈智能大数据分析 ⌋ ⌋ ⌋ 智能大数据分析是指利用先进的技术和算法对大规模数据进行深入分析和挖掘,以提取有价值的信息和洞察。它结合了大数据技术、人工智能(AI)、机器学习(ML&a…...
【极速版 -- 大模型入门到进阶】除了 Prompting, 大模型还能如何被应用?
文章目录 大模型应用 -- Generative AI Projects🌊 大模型应用的时效优势🌊 大模型应用的方式 - Technology Options应用方式一 🐟 Prompting:最简单快速应用方式二🐟 Retrieval augmented generation (RAG)࿱…...
[Unity]发包前遇到的坑之GridLayoutGroup
发包前禁用了UI上面一个调试页面A后,发现无法正确获取某一个用了GridLayoutGroup组件的所有子物体的世界坐标。 一顿研究之后发现,在Start的时候想要正确获取其坐标,需要强制刷新一次布局,方法如下: UnityEngine.U…...
【C++】IO 流
文章目录 👉C 语言的输入与输出👈👉流是什么👈👉C IO 流👈C 标准 IO 流C 和 C 语言的输入格式问题C 的多次输入内置类型和自定义类型的转换日期的多次输入C 文件 IO 流文本文件和二进制文件的读写 …...
Public Key Retrieval is not allowed 解决方法
如图:我的报错是Public Key Retrieval is not allowed,我的前后端都能正常加载,但是在请求数据库时就会报错如下: 解决办法: 在 application.yaml 中的数据库设置地方加上allowPublicKeyRetrievaltrue,然后…...
大数据原生集群 (Hadoop3.X为核心) 本地测试环境搭建二
本篇安装软件版本 mysql5.6 spark3.2.1-hadoop3.2 presto0.272 zeppelin0.11.2 kafka_2.13_3.7.2 mysql 安装步骤见-》 https://blog.csdn.net/dudadudadd/article/details/110874570 spark 安装步骤见-》https://blog.csdn.net/dudadudadd/article/details/109719624 安装…...
服务器引导异常,Grub报错: error: ../../grub-core/fs/fshelp.c:258:file xxxx.img not found.
服务器引导异常,Grub报错: error: ../../grub-core/fs/fshelp.c:258:file xxxx.img not found. 1. 故障现象2. 解决思路3. 故障分析4. 案件回溯5. 解决问题 1. 故障现象 有一台服务器业务报无法连接. 尝试用Ping命令发现无法ping通. 通过控制台查看发现有以下报错: error: ..…...
RabbitMQ-消息入队
1 分布式异步的问题 对于一个业务线的处理,如果是一个完整的处理,应该是消息正 常进入队列,同时消息正常被消费掉。 问题来了: 生产者发送消息,在传输过程中,消息丢失了,咋办? 消息发…...
Angular-生命周期及钩子函数
什么是生命周期 Angular 创建和渲染组件及其子组件,当它们绑定的属性发生变化时检查它们,并在从 DOM 中移除它之前销毁它们。生命周期函数通俗的讲就是组件创建、组件更新、组件销毁的时候会触发的一系列的方法。当 Angular 使用构造函数新建一个组件或…...
算法-高精度问题(带图详细解读~)
今天来分享四道大数运算的模板题. 目录 1. 大数相加2. 大数相减3. 大数相乘4. 大数相除 1. 大数相加 题目链接: LINK 基本思路: 存入数组, 模拟运算. 逆序字符串补零操作依次取数据, 依次相加 3-1 加: (t-ret s1[i] s2[i] carry) % 10; 3-2 进: (t-ret s1[i] s2[i] car…...
MC1.12.2 macOS高清修复OptiFine运行崩溃
最近在玩RLCraft,在windows中运行正常的,移植到macOS中发现如果加载OptiFine模组就会崩溃 报错日志 报错日志如下,其中已经包含了各种版本信息,我就不单独说明了。这里说一下,报错的时候用的是oracle jdk x64的&…...
Spring Boot教程之五十六:用 Apache Kafka 消费 JSON 消息
Spring Boot | 如何使用 Apache Kafka 消费 JSON 消息 Apache Kafka 是一个流处理系统,可让您在进程、应用程序和服务器之间发送消息。在本文中,我们将了解如何使用 Apache Kafka 在 Spring Boot 应用程序的控制台上发布 JSON 消息。 为了了解如何创建 …...
远程和本地文件的互相同步
文章目录 1、rsync实现类似git push pull功能1. 基础概念2. 示例操作3. 定制化和进阶用法4. 定时同步(类似自动化) 2 命令简化1. 动态传参的脚本2. Shell 函数支持动态路径3. 结合环境变量和参数(更简洁)4. Makefile 支持动态路径…...
在ES6模块中导入和导出
在ES6模块中导入和导出 以最简单的例子举例 //shoppingCart.js //导出模块 console.log(导出模块);//script.js //导出模块 import ./shoppingCart.js; console.log(导入模块);所以要导入其他模块必须指定类型 <script type"Modules" defer src"script.js&…...
centos使用dpdk库
yum -y install dpdk dpdk-devel 在 C 中使用 DPDK(Data Plane Development Kit)库通常涉及到以下几个步骤:安装 DPDK、配置编译环境、编写 C 代码并链接 DPDK 库。以下是如何在 C 中引用和使用 DPDK 的详细步骤。 1. 安装 DPDK 首先&#…...
ChatGLM:从GLM-130B到GLM-4全系列大语言模型
摘要 我们介绍了ChatGLM,这是一个不断进化的大语言模型系列,我们一直在持续开发中。本报告主要聚焦于GLM-4语言系列,包括GLM-4、GLM-4-Air和GLM-4-9B。它们代表了我们从ChatGLM前三代中汲取的所有见解和经验教训所训练出的最强大模型。迄今为…...
EF Core分页
Skip(3).Take(8) 最好显式指定排序规则需要知道满足条件的数据的总条数: 用IQueryable的复用 LongCount和Count页数:long pageCount (long)Math.Ceiling(count * 1.0 / pageSize); class Program {static async Task Main(string[] args){using (MyDbC…...
一种ESP8266+OLED时间天气显示
在当今这个信息爆炸的时代,人们对于获取实时信息的需求日益增长,尤其是在时间与天气这两个与日常生活息息相关的方面。而将 ESP8266 与 OLED 显示屏相结合制作的时钟兼天气显示设备,凭借其便携性、实时性以及低成本等优势,成为了众…...
LabVIEW光流跟踪算法
1. 光流跟踪算法的概述 光流(Optical Flow)是一种图像处理技术,用于估算图像中像素点的运动。通过比较连续帧图像,光流算法可以分析图像中的运动信息,广泛用于目标跟踪、运动检测和视频处理等场景。该示例使用了NI Vi…...
Nacos 配置与服务注册问题排查指南
Nacos 配置与服务注册问题排查指南 1. Nacos 配置文件优先级 在 Spring Boot 应用中,配置文件的优先级从高到低依次为: bootstrap.propertiesbootstrap.ymlapplication.propertiesapplication.yml 2. Nacos 配置中心配置示例 以下是一个典型的 Naco…...
浅谈云计算06 | 云管理系统架构
云管理系统架构 一、云管理系统架构(一)远程管理系统(二)资源管理系统(三)SLA 管理系统(四)计费管理系统 二、安全与可靠性保障(一)数据安全防线(…...
system securiry: supervisor password required
报错解释: 这个错误表明系统安全模块(如SELinux或AppArmor)需要超级用户(通常是root)的密码来确认一个操作。这通常发生在尝试进行某些需要高级权限的系统更改时。 解决方法: 如果你拥有root权限࿰…...
【Python基础知识】pdb-Python的调试器的常用命令和使用示例
使用pdb的情形 多数时候,可以使用PyCharm、VSCode等现代化IDE进行代码的调试 对于远程服务器中运行的服务,本地无法复现时,可以使用 Python自带的pdb进行调试 1 代码中断点埋桩 中断进入调试器的典型用法是 在需要调试的地方插入以下代码: …...
C++ STL之容器介绍(vector、list、set、map)
1 STL基本概念 C有两大思想,面向对象和泛型编程。泛型编程指编写代码时不必指定具体的数据类型,而是使用模板来代替实际类型,这样编写的函数或类可以在之后应用于各种数据类型。而STL就是C泛型编程的一个杰出例子。STL(Standard …...
【向量数据库 Milvus】Milvus 2.5版本CPU 安装单机版
以下是Milvus 2.5版本单机安装的步骤: 前提条件 系统可以使用centos或者ubuntu。系统已经安装docker和docker-compose。 下载并编辑docker-compose.yml 进入Milvus的GitHub项目主页查看最新版本的Milvus,下载对应版本的docker-compose.yml文件&#…...
[Do374]Ansible一键搭建sftp实现用户批量增删
[Do374]Ansible一键搭建sftp实现用户批量增删 1. 前言2. 思路3. sftp搭建及用户批量新增3.1 配置文件内容3.2 执行测试3.3 登录测试3.4 确认sftp服务器配置文件 4. 测试删除用户 1. 前言 最近准备搞一下RHCA LV V,外加2.9之后的ansible有较大变化于是练习下Do374的课程内容. 工…...
系统认识数据分析
什么是数据分析? 数据分析是指用适当的统计分析方法对收集来的大量数据进行分析,将它们加以汇总和理解并消化,以求最大化地开发数据的功能,发挥数据的作用。数据分析是为了提取有用信息和形成结论而对数据加以详细研究和概括总结的…...
Cherno C++学习笔记 P52 处理多返回值
在这篇文章当中,我们解决一下如何用C的函数处理多返回值的问题。 在有些情况下,我们希望我们的函数可以返回多个返回值,比如返回两个string或者是一个int加上一个string。如果我们用的是python之类的语言的话,那这个事情其实是很…...
Android车机DIY开发之学习篇(一)编译UBOOT以正点原子为例
Android车机DIY开发之学习篇(一)编译UBOOT以正点原子为例 1.代码在u-boot文件夹下 2.在 U-Boot 源码目录下执行如下命令编译 U-Boot: ./make.sh rk3588生成两个文件 ### uboot.img 对应<SDK>/uboot/uboot.img ### rk3588_spl_loader_v1.13.113.bin 对应<…...
扩散模型、原型网络以及肿瘤微环境解析等名词出现在基金立项名单中,它们各自的应用现状如何?|文献速递·25-01-10
小罗碎碎念 昨晚看到了云南省2025年自然科学基金立项的名单,今天把医工交叉的项目挑出来和大家分享一下。 今天分享的文献,灵感来源于2025年的基金,我会先简单分析一下基金的情况,然后再和大家分享三篇与立项基金相关的文献。 总共…...
【Java设计模式-4】策略模式,消灭if/else迷宫的利器
各位Java编程小伙伴们!今天咱们要一起探索一个超级厉害的Java设计模式——策略模式,它就像是一把神奇的魔法剑,专门用来斩断那些让我们代码变得乱糟糟的if/else语句迷宫! 一、if/else的烦恼 在编程的奇妙世界里,我们…...
10分钟快速了解OceanGPT(沧渊)
10分钟快速了解OceanGPT(沧渊) 海洋科学任务的大语言模型——OceanGPT OceanGPT是如何训练的?为了训练 OceanGPT (沧渊) ,收集了一个跨越多个领域的海洋科学语料库。由于每个子领域和主题都有其独特的数据特征和模式,因此提出了一个特定于领域的指令生成框架,称为 DoDirec…...
学习及笔记
1、计算md5 md5sum 文件名 2、跨服务器复制 scp 文件 目标用户名目标Ip:目标路径 3、curl curl -X POST http://10.105.2.46/getUerls -H "Content-Type: application/json" -d {"id": 379, "userId": "lyc", "password":…...
TensorFlow Quantum快速编程(基本篇)
一、TensorFlow Quantum 概述 1.1 简介 TensorFlow Quantum(TFQ)是由 Google 开发的一款具有开创性意义的开源库,它宛如一座桥梁,巧妙地将量子计算与 TensorFlow 强大的机器学习功能紧密融合。在当今科技飞速发展的时代,传统机器学习虽已取得诸多瞩目成就,然而面对日益…...