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

牛客网-----跳石头

题目描述:

一年一度的“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有N块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M块岩石(不能移走起点和终点的岩石)。


 输入描述:

输入文件第一行包含三个整数L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。
接下来 N行,每行一个整数,第i行的整数Di(0 < Di< L)表示第i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

输出描述:

输出文件只包含一个整数,即最短跳跃距离的最大值。


示例1:

输入 :


25 5 2 

11

14

17

21

输出:   

4

说明:

将与起点距离为2和14的两个岩石移走后,最短的跳跃距离为4(从与起点距离17的岩石跳到距离21的岩石,或者从距离21的岩石跳到终点)。


二分查找算法板子(整数):

1、左面模板

//左面模板
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;
}

2、右面模板

//右面模板
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}

 根据样例,图解如下:

 根据如上图解,我们可以 看出根据  d  的增加,移动石头次数 m 也是逐渐增加的,所以d = 5不行,那么说明d > 5 的 情况都是不行的,所以答案是d = 4,移动次数m = 2


代码思路: 

1、写好对应的数组
2、确定好二分的板子
3、写好check函数

AC代码如下: 

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N  = 50010;
int L,n,m;
int a[N];bool check(int x)
{//cnt,表示移动石头的次数,last 表示指向没有移动过的石头int cnt = 0,last  = 0;for(int i=1;i<=n;i++){//判断一下两个石头之间的距离是否小于这个最短跳跃距离if(a[i] - a[last] < x){cnt ++; //移动石头次数增加}else{last = i; //last永远指在没被挪动的石头上面}if(cnt > m) return false;}return true;
}int main()
{scanf("%d %d %d",&L,&n,&m);//因为算是起点和终点的话是N+2个数for(int i=1;i<=n;i++) scanf("%d",&a[i]);a[n+1] = L; //终点int l = 1,r = L;/*这里为啥不用左模板 是因为 在一个有序的数组下,我们想要找到最长的那个一定是在最右边。*/while(l < r){int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}cout << l << endl;return 0;
}

如果last那块不懂的话大家可以拿题目给的样例去手动模拟一下,好好理解代码的过程,感谢观看~

相关文章:

牛客网-----跳石头

题目描述&#xff1a; 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行&#xff0c;河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间&#xff0c;有N块岩石(不含起点和终点的岩石)。在比赛过程中&#xff0…...

用ChatGPT教学、科研!大学与OpenAI合作

亚利桑那州立大学&#xff08;简称“ASU”&#xff09;在官网宣布与OpenAI达成技术合作。从2024年2月份开始&#xff0c;为所有学生提供ChatGPT企业版访问权限&#xff0c;主要用于学习、课程作业和学术研究等。 为了帮助学生更好地学习ChatGPT和大语言模型产品&#xff0c;AS…...

运维平台介绍:视频智能运维平台的视频质量诊断分析和告警中心

目 录 一、视频智能运维平台介绍 &#xff08;一&#xff09;平台概述 &#xff08;二&#xff09;结构图 &#xff08;三&#xff09;功能介绍 1、运维监控 2、视频诊断 3、巡检管理 4、告警管理 5、资产管理 6、工单管理 7、运维…...

GAMES104-现代游戏引擎:从入门到实践 - 物理引擎课程笔记汇总

文章目录 0 入门资料1 物理引擎基本概念Actor & shapesRigid body dynamicsCollision DetectionCollision Resolution 应用与实践Character controllerRagdoll 0 入门资料 GAMES104-现代游戏引擎&#xff1a;从入门到实践_课程视频_bilibiliGAMES104官方账号 - 知乎课程主页…...

【linux】Xorg的工作原理

介绍 在linux系统上执行nvidia-smi时&#xff0c;总有一个进程占用gpu。 1 N/A N/A 2174 G /usr/lib/xorg/Xorg 4MiB /usr/lib/xorg/Xorg 是与X Window System&#xff08;简称X11或X&#xff09;相关的一个应用程序。X Window System是一个…...

02-docker下部署seata

官方部署文档 http://seata.io/zh-cn/docs/ops/deploy-by-docker 配置参数说明 http://seata.io/zh-cn/docs/user/configurations 1、镜像拉取 docker pull seata-server2、复制配置文件 mkdir /home/server/seata cd /home/server/seata docker run -d -p 8091:8091 -p 709…...

回归预测 | Matlab实现GA-APSO-MBP、GA-MBP、MBP、BP多输入单输出回归预测

回归预测 | Matlab实现GA-APSO-MBP、GA-MBP、MBP、BP多输入单输出回归预测 目录 回归预测 | Matlab实现GA-APSO-MBP、GA-MBP、MBP、BP多输入单输出回归预测预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab实现GA-APSO-MBP、GA-MBP、MBP、BP多输入单输出回归预测&…...

精益生产咨询背后的秘密:企业如何实现价值最大化

精益生产&#xff0c;起源于丰田生产系统&#xff0c;是一种集中于削减浪费、优化流程、提升顾客价值的生产方法。它的核心在于确保每一步生产过程都能为顾客创造价值。以下是实现精益生产咨询的详细步骤&#xff1a; 1.确定客户价值 一切从顾客需求出发。企业需深入理解顾客…...

创建SERVLET

创建SERVLET 要创建servlet,需要执行以下任务: 编写servlet。编译并封装servlet。将servlet部署为Java EE应用程序。通过浏览器访问servlet。编写servlet 要编写servlet,需要扩展HttpServlet接口的类。编写servlet是,需要合并读取客户机请求和返回响应的功能。 读取和处…...

python算法与数据结构(搜索算法和拓扑排序算法)---深度优先搜索

课程目标 了解树/图的深度遍历&#xff0c;宽度遍历基本原理&#xff1b;会使用python语言编写深度遍历&#xff0c;广度遍历代码&#xff1b;掌握拓扑排序算法 搜索算法的意义和作用 搜索引擎 提到搜索两个子&#xff0c;大家都应该会想到搜索引擎&#xff0c;搜索引擎的基…...

thinkphp5实战之phpstudy v8环境搭建,解决Not Found找不到路径问题

引言 thinkphp以快速、简约的大道至简的思想广受欢迎&#xff0c;适合开发小型项目。本地环境下&#xff0c;phpstudy v8是一款比较优秀的集成环境软件。部署完项目后&#xff0c;访问的时候傻眼&#xff0c;报错。 解决方案 不要慌&#xff0c;这个是伪静态的原因。选择apach…...

fastjson-BCEL不出网打法原理分析

FastJson反序列化漏洞 与原生的 Java 反序列化的区别在于&#xff0c;FastJson 反序列化并未使用 readObject 方法&#xff0c;而是由 FastJson 自定一套反序列化的过程。通过在反序列化的过程中自动调用类属性的 setter 方法和 getter 方法&#xff0c;将JSON 字符串还原成对…...

部署mysql主从同步,部署mysql数据读写分离结构+mycat2

主要命令 [rootmysql59 ~]# yum –y install mysql-server mysql[rootmysql59 ~]# systemctl start mysqld[rootmysql59 ~]# vim /etc/my.cnf.d/mysql-server.cnf[mysqld]server-id59log-binmysql59:wq[rootmysql59 ~]# systemctl restart mysqld//用户授权[rootmysql59 ~]# my…...

【最新!超详细C++入门】

01_C语言基础 一、课程目标 1、掌握 C基本语法&#xff1a;变量、常量、注释、标识符命名规范 2、掌握C数据类型 3、掌握C的输入和输出 4、掌握C运算符和表达式 5、掌握条件语句 6、掌握循环语句 二、课程内容 1 C初识 1.1 第一个C程序 编写一个C程序总共分为4个步骤…...

【Linux】【实战系列】10 分钟掌握日常开发中 Linux 网络处理相关命令

文章目录 lsofnetstatpingnslookupsshssh-keygenscpsftp 网络工具 curl网络工具 wget最后个人简介 hello&#xff0c;大家好&#xff0c;我是 Lorin&#xff0c;上一期和大家分享一期日常开发中常用的 Linux 文件和文本命令实战教学&#xff0c;这一期给大家带来常用的网络处理…...

语义分割常用评价指标

在图像处理领域中&#xff0c;语义分割是很重要的一个任务。在实际项目开发中,评估模型预测效果以及各指标的含义对于优化模型极为重要。 本文将主要评价指标的计算算法进行了详细说明,并加上注释解释每个指标的含义。这对理解各指标背后的数学原理以及能否在实践中应用或许有…...

从0开始学习C++ 第一课:你的第一个C++程序

第一课&#xff1a;你的第一个C程序 当然可以。让我们从C的基础开始&#xff0c;我们的第一课将覆盖以下几个主题&#xff1a; 程序结构编写和运行你的第一个C程序基本的输入输出&#xff08;I/O&#xff09; 第一课&#xff1a;你的第一个C程序 在C中&#xff0c;所有的程…...

Dubbo-admin监控中心

监控中心 Dubbo-admin监控中心执行操作启动provider和consumer项目进行测试总体流程 Dubbo-admin监控中心 dubbo-admin下载路径 git clone https://github.com/apache/dubbo-admin.git图1-1 dubbo-admin项目文件展示 执行操作 # 启动zookeeper# 前端 cd dubbo-admin-ui npm i…...

216. 组合总和 III - 力扣(LeetCode)

题目描述 找出所有相加之和为 n 的 k 个数的组合&#xff0c;且满足下列条件&#xff1a; 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次&#xff0c;组合可以以任何顺序返回。 输入示例 k 3, n 7输出示例 [[1,2,…...

LeetCode-题目整理【5】:O(1) 时间插入、删除和获取随机元素

RandomizedSet结构体存在切片和哈希表的原因&#xff1a; 变长数组由于可以根据下标定位到特定元素&#xff0c;因此可以在 O(1)的时间内完成获取随机元素操作&#xff0c;但是由于无法在 O(1) 的时间内判断元素是否存在&#xff0c;因此不能在 O(1) 的时间内完成插入和删除操作…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...