洛谷 P2678 [NOIP2015 提高组] 跳石头 (Java)
洛谷 P2678 [NOIP2015 提高组] 跳石头 (Java)
传送门:P2678 [NOIP2015 提高组] 跳石头
题目:
[NOIP2015 提高组] 跳石头
题目背景
NOIP2015 Day2T1
题目描述
一年一度的“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N N N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M M M 块岩石(不能移走起点和终点的岩石)。
输入格式
第一行包含三个整数 L , N , M L,N,M L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。保证 L ≥ 1 L \geq 1 L≥1 且 N ≥ M ≥ 0 N \geq M \geq 0 N≥M≥0。
接下来 N N N 行,每行一个整数,第 i i i 行的整数 D i ( 0 < D i < L ) D_i\,( 0 < D_i < L) Di(0<Di<L), 表示第 i i i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。
输出格式
一个整数,即最短跳跃距离的最大值。
样例 #1
样例输入 #1
25 5 2
2
11
14
17
21
样例输出 #1
4
提示
输入输出样例 1 说明
将与起点距离为 2 2 2 和 14 14 14 的两个岩石移走后,最短的跳跃距离为 4 4 4(从与起点距离 17 17 17 的岩石跳到距离 21 21 21 的岩石,或者从距离 21 21 21 的岩石跳到终点)。
数据规模与约定
对于 20 % 20\% 20%的数据, 0 ≤ M ≤ N ≤ 10 0 \le M \le N \le 10 0≤M≤N≤10。
对于 50 % 50\% 50% 的数据, 0 ≤ M ≤ N ≤ 100 0 \le M \le N \le 100 0≤M≤N≤100。
对于 100 % 100\% 100% 的数据, 0 ≤ M ≤ N ≤ 50000 , 1 ≤ L ≤ 1 0 9 0 \le M \le N \le 50000,1 \le L \le 10^9 0≤M≤N≤50000,1≤L≤109。
分析:
题目要我们求最短跳跃距离(1 <= ans <= L),我们可以二分起点到终点的长度获得答案。
在每次二分时,我们定义now(当前所在的位置)和step(搬走石头的数量)。
如果每次跳跃 a[i]-now 的距离 大于 mid,说明 a[i] 这块石头需要搬走;否则我们就可以跳到这块石头上,更新 now 。
如果step 大于 m ,说明需要搬走的石头太多,我们不能跳跃这么多,缩小跳跃距离,更新r = mid-1;否则,需要搬走的石头 <= m,说明我们至少可以跳跃这么多 ans = mid,继续搜索更大跳跃距离,更新 l = mid +1。
代码:
import java.util.Scanner;public class Main {public static void main(String[] args) { Scanner sc = new Scanner(System.in);int L = sc.nextInt();int n = sc.nextInt();int m = sc.nextInt();int [] a = new int [n+10];for(int i = 1;i <= n;i++) a[i] = sc.nextInt();a[n+1] = L;int l = 0;int r = L;int ans = 0;// 二分获得跳跃的最小距离while(l <= r) {// 跳跃的距离int mid = (l+r)/2;// now表示我现在的位置,step表示搬走石头的数量int now = 0;int step = 0;for(int i = 1;i <= n+1;i++) {// 二分小于mid,这块石头要搬走if(a[i]-now < mid) step++;// 跳到这块石头上else now = a[i];}// 搬走的石头大于m,不可以if(step > m) {r = mid-1;}else {l = mid+1;ans = mid;}//System.out.printf("l r ans:%d %d %d\n",l,r,ans);}System.out.println(ans);}
}
相关文章:
洛谷 P2678 [NOIP2015 提高组] 跳石头 (Java)
洛谷 P2678 [NOIP2015 提高组] 跳石头 (Java) 传送门:P2678 [NOIP2015 提高组] 跳石头 题目: [NOIP2015 提高组] 跳石头 题目背景 NOIP2015 Day2T1 题目描述 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行&…...
第2讲投票系统后端架构搭建
创建项目时,随机选择一个,后面会生成配置properties文件 生成文件 maven-3.3.3 设置阿里云镜像 <?xml version"1.0" encoding"UTF-8"?><!-- Licensed to the Apache Software Foundation (ASF) under one or more cont…...
Flask 入门7:使用 Flask-Moment 本地化日期和时间
如果Web应用的用户来自世界各地,那么处理日期和时间可不是一个简单的任务。服务器需要统一时间单位,这和用户所在的地理位置无关,所以一般使用协调世界时(UTC)。不过用户看到 UTC 格式的时间会感到困惑,他们…...
FileZilla Server 1.8.1内网搭建
配置环境服务器服务器下载服务器配置服务器配置 Server - ConfigureServer Listeners - Port 协议设置 Protocols settingsFTP and FTP over TLS(FTPS) Rights management(权利管理)Users(用户) 客户端建立连接 配置环境 服务器处于局域网内: 客户端 < -访问- > 公网 &l…...
C++LNK1207中的 PDB 格式不兼容;请删除并重新生成
在打开别人发的C文件时,可能出现该报错 解决办法 打开资源管理器,找到原来的路径 进入Debug, 找到对应的PDB文件删除即可。...
小白学习Halcon100例:如何利用动态阈值分割图像进行PCB印刷缺陷检测?
文章目录 *读入图片*关闭所有窗口*获取图片尺寸*根据图片尺寸打开一个窗口*在窗口中显示图片* 缺陷检测开始 ...*1.开运算 使用选定的遮罩执行灰度值开运算。*2.闭运算 使用选定的遮罩执行灰度值关闭运算*3.动态阈值分割 使用局部阈值分割图像显示结果*显示原图*设置颜色为红色…...
车载诊断协议DoIP系列 —— 车载以太网诊断需求规范(网关、路由)
车载诊断协议DoIP系列 —— 车载以太网诊断需求规范(网关、路由) 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师(Wechat:gongkenan2013)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 本就是小人物,输了就是输了,不要在意别人怎么看自…...
面试官:介绍一下MVC框架
前言 大家好,我是chowley,MVC相信大家都听说过,今天我就记录一下我心中的MVC框架 MVC(Model-View-Controller)是一种软件设计模式,用于将应用程序分为三个核心部分:模型(Model&…...
C++ new 和 malloc 的区别?
相关系列文章 C内存分配策略-CSDN博客 目录 1.引言 2.区别 2.1.申请的内存分配区域 2.2.类型安全和自动大小计算 2.3.构造函数和析构函数的调用 2.4.异常处理 2.5.配对简便性 2.6.new 的重载 2.7.关键字和操作符 3.总结 1.引言 new 和 delete 在 C 中被引入…...
腾讯云4核8G服务器多少钱?
腾讯云4核8G服务器多少钱?轻量应用服务器4核8G12M带宽一年446元、646元15个月,云服务器CVM标准型S5实例4核8G配置价格15个月1437.3元,5年6490.44元,标准型SA2服务器1444.8元一年,在txy.wiki可以查询详细配置和精准报价…...
独孤思维:看到副业坚持4年,我震惊了
01 新人写作,不要写纯理论的东西,也不要写自我高潮的内容。 都写点接地气,多实操的内容。 比如,独孤现在每一篇短文写作,都会引入一个案例。 这样,对于很多读者来说,更好理解,能…...
kali无线渗透之wps加密模式和破解12
WPS(Wi-Fi Protected Setup,Wi-Fi保护设置)是由Wi-Fi联盟推出的全新Wi-Fi安全防护设定标准。该标准推出的主要原因是为了解决长久以来无线网络加密认证设定的步骤过于繁杂之弊病,使用者往往会因为步骤太过麻烦,以致干脆不做任何加密安全设定&…...
gorm day8
gorm day8 gorm Has Many关系gorm Many To Many关系 gorm Has Many关系 Has Many 在GORM(Go的一个对象关系映射库)中,“Has Many” 关系表示一个实体与另一个实体之间的一对多关系。这意味着一个实体(我们称之为"父"…...
【计算机网络】【练习题及解答】【新加坡南洋理工大学】【Computer Control Network】【Exercise Solution】
说明: 个人资料,仅供学习使用,版权归校方所有。 一、题目描述 该问题接上期博文【练习题及解答】,描述网络通信中的链路效率(Link Efficiency),即Link Utilization的计算。(此处认…...
c语言操作符(上
目录 编辑 原码、反码、补码 1、正数 2、负数 3、二进制计算1-1 移位操作符 1、<<左移操作符 2、>>右移操作符 位操作符&、|、^、~ 1、&按位与 2、|按位或 3、^按位异或 特点 4、~按位取反 原码、反码、补码 1、正数 原码 反码 补码相同…...
Linux后台长时间以及定时运行python脚本
1.使用nohup命令:nohup命令用于运行一个命令,在用户退出登录后仍然保持运行。 在命令行输入:nohup python绝对路径 脚本的绝对路径 & python的绝对路径,在命令行输入:which python 例如:nohup /usr…...
计算机二级数据库之数据模型
数据模型 模型的概念 模型的介绍模型是对现实世界特征的模拟和抽象, 数据模型的概念: 数据模型是对现实世界中数据特征的抽象,描述的是数据的共性。 数据模型是用来在数据库中抽象、表示和处理现实世界中的数据和信凹。 其相关的共同特…...
Linux多线程[二]
引入知识 进程在线程内部执行是OS的系统调度单位。 内核中针对地址空间,有一种特殊的结构,VM_area_struct。这个用来控制虚拟内存中每个malloc等申请的空间,来区别每个malloc的是对应的堆区哪一段。OS可以做到资源的精细度划分。 对于磁盘…...
宿舍报修|宿舍报修小程序|基于微信小程序的宿舍报修系统的设计与实现(源码+数据库+文档)
宿舍报修小程序目录 目录 基于微信小程序的宿舍报修系统的设计与实现 一、前言 二、系统功能设计 三、系统实现 1、学生信息管理 2 维修人员管理 3、故障上报管理 4、论坛信息管理 四、数据库设计 1、实体ER图 五、核心代码 六、论文参考 七、最新计算机毕设选题推…...
浅谈开源软件的影响力
目录 1. 技术发展推动者: 2. 社区生态构建者: 3. 经济模式创新者: 4. 全球合作促进者: 5. 安全性贡献者: 6. 教育与人才培养: 7. 总结来说 不是每个人都能做自己想做的事,成为自己想成为…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
