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

洛谷 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 L1 N ≥ M ≥ 0 N \geq M \geq 0 NM0

接下来 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 0MN10
对于 50 % 50\% 50% 的数据, 0 ≤ M ≤ N ≤ 100 0 \le M \le N \le 100 0MN100
对于 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 0MN50000,1L109

分析:

题目要我们求最短跳跃距离(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) 传送门&#xff1a;P2678 [NOIP2015 提高组] 跳石头 题目&#xff1a; [NOIP2015 提高组] 跳石头 题目背景 NOIP2015 Day2T1 题目描述 一年一度的“跳石头”比赛又要开始了&#xff01; 这项比赛将在一条笔直的河道中进行&…...

第2讲投票系统后端架构搭建

创建项目时&#xff0c;随机选择一个&#xff0c;后面会生成配置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应用的用户来自世界各地&#xff0c;那么处理日期和时间可不是一个简单的任务。服务器需要统一时间单位&#xff0c;这和用户所在的地理位置无关&#xff0c;所以一般使用协调世界时&#xff08;UTC&#xff09;。不过用户看到 UTC 格式的时间会感到困惑&#xff0c;他们…...

FileZilla Server 1.8.1内网搭建

配置环境服务器服务器下载服务器配置服务器配置 Server - ConfigureServer Listeners - Port 协议设置 Protocols settingsFTP and FTP over TLS(FTPS) Rights management(权利管理)Users(用户) 客户端建立连接 配置环境 服务器处于局域网内: 客户端 < -访问- > 公网 &l…...

C++LNK1207中的 PDB 格式不兼容;请删除并重新生成

在打开别人发的C文件时&#xff0c;可能出现该报错 解决办法 打开资源管理器&#xff0c;找到原来的路径 进入Debug&#xff0c; 找到对应的PDB文件删除即可。...

小白学习Halcon100例:如何利用动态阈值分割图像进行PCB印刷缺陷检测?

文章目录 *读入图片*关闭所有窗口*获取图片尺寸*根据图片尺寸打开一个窗口*在窗口中显示图片* 缺陷检测开始 ...*1.开运算 使用选定的遮罩执行灰度值开运算。*2.闭运算 使用选定的遮罩执行灰度值关闭运算*3.动态阈值分割 使用局部阈值分割图像显示结果*显示原图*设置颜色为红色…...

车载诊断协议DoIP系列 —— 车载以太网诊断需求规范(网关、路由)

车载诊断协议DoIP系列 —— 车载以太网诊断需求规范(网关、路由) 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师(Wechat:gongkenan2013)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 本就是小人物,输了就是输了,不要在意别人怎么看自…...

面试官:介绍一下MVC框架

前言 大家好&#xff0c;我是chowley&#xff0c;MVC相信大家都听说过&#xff0c;今天我就记录一下我心中的MVC框架 MVC&#xff08;Model-View-Controller&#xff09;是一种软件设计模式&#xff0c;用于将应用程序分为三个核心部分&#xff1a;模型&#xff08;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 中被引入&#xf…...

腾讯云4核8G服务器多少钱?

腾讯云4核8G服务器多少钱&#xff1f;轻量应用服务器4核8G12M带宽一年446元、646元15个月&#xff0c;云服务器CVM标准型S5实例4核8G配置价格15个月1437.3元&#xff0c;5年6490.44元&#xff0c;标准型SA2服务器1444.8元一年&#xff0c;在txy.wiki可以查询详细配置和精准报价…...

独孤思维:看到副业坚持4年,我震惊了

01 新人写作&#xff0c;不要写纯理论的东西&#xff0c;也不要写自我高潮的内容。 都写点接地气&#xff0c;多实操的内容。 比如&#xff0c;独孤现在每一篇短文写作&#xff0c;都会引入一个案例。 这样&#xff0c;对于很多读者来说&#xff0c;更好理解&#xff0c;能…...

kali无线渗透之wps加密模式和破解12

WPS(Wi-Fi Protected Setup&#xff0c;Wi-Fi保护设置)是由Wi-Fi联盟推出的全新Wi-Fi安全防护设定标准。该标准推出的主要原因是为了解决长久以来无线网络加密认证设定的步骤过于繁杂之弊病&#xff0c;使用者往往会因为步骤太过麻烦&#xff0c;以致干脆不做任何加密安全设定&…...

gorm day8

gorm day8 gorm Has Many关系gorm Many To Many关系 gorm Has Many关系 Has Many 在GORM&#xff08;Go的一个对象关系映射库&#xff09;中&#xff0c;“Has Many” 关系表示一个实体与另一个实体之间的一对多关系。这意味着一个实体&#xff08;我们称之为"父"…...

【计算机网络】【练习题及解答】【新加坡南洋理工大学】【Computer Control Network】【Exercise Solution】

说明&#xff1a; 个人资料&#xff0c;仅供学习使用&#xff0c;版权归校方所有。 一、题目描述 该问题接上期博文【练习题及解答】&#xff0c;描述网络通信中的链路效率&#xff08;Link Efficiency&#xff09;&#xff0c;即Link Utilization的计算。&#xff08;此处认…...

c语言操作符(上

目录 ​编辑 原码、反码、补码 1、正数 2、负数 3、二进制计算1-1 移位操作符 1、<<左移操作符 2、>>右移操作符 位操作符&、|、^、~ 1、&按位与 2、|按位或 3、^按位异或 特点 4、~按位取反 原码、反码、补码 1、正数 原码 反码 补码相同…...

Linux后台长时间以及定时运行python脚本

1.使用nohup命令&#xff1a;nohup命令用于运行一个命令&#xff0c;在用户退出登录后仍然保持运行。 在命令行输入&#xff1a;nohup python绝对路径 脚本的绝对路径 & python的绝对路径&#xff0c;在命令行输入&#xff1a;which python 例如&#xff1a;nohup /usr…...

计算机二级数据库之数据模型

数据模型 模型的概念 模型的介绍模型是对现实世界特征的模拟和抽象&#xff0c; 数据模型的概念&#xff1a; 数据模型是对现实世界中数据特征的抽象&#xff0c;描述的是数据的共性。 数据模型是用来在数据库中抽象、表示和处理现实世界中的数据和信凹。 其相关的共同特…...

Linux多线程[二]

引入知识 进程在线程内部执行是OS的系统调度单位。 内核中针对地址空间&#xff0c;有一种特殊的结构&#xff0c;VM_area_struct。这个用来控制虚拟内存中每个malloc等申请的空间&#xff0c;来区别每个malloc的是对应的堆区哪一段。OS可以做到资源的精细度划分。 对于磁盘…...

宿舍报修|宿舍报修小程序|基于微信小程序的宿舍报修系统的设计与实现(源码+数据库+文档)

宿舍报修小程序目录 目录 基于微信小程序的宿舍报修系统的设计与实现 一、前言 二、系统功能设计 三、系统实现 1、学生信息管理 2 维修人员管理 3、故障上报管理 4、论坛信息管理 四、数据库设计 1、实体ER图 五、核心代码 六、论文参考 七、最新计算机毕设选题推…...

浅谈开源软件的影响力

目录 1. 技术发展推动者&#xff1a; 2. 社区生态构建者&#xff1a; 3. 经济模式创新者&#xff1a; 4. 全球合作促进者&#xff1a; 5. 安全性贡献者&#xff1a; 6. 教育与人才培养&#xff1a; 7. 总结来说 不是每个人都能做自己想做的事&#xff0c;成为自己想成为…...

多角色语音合成解决方案:Chatterbox技术实现与应用指南

多角色语音合成解决方案&#xff1a;Chatterbox技术实现与应用指南 【免费下载链接】chatterbox Open source TTS model 项目地址: https://gitcode.com/GitHub_Trending/chatterbox7/chatterbox 在数字化内容创作与智能交互领域&#xff0c;语音合成技术正经历从单一语…...

因果模型评估完全手册:Python指标与验证方法详解

因果模型评估完全手册&#xff1a;Python指标与验证方法详解 【免费下载链接】python-causality-handbook 项目地址: https://gitcode.com/gh_mirrors/py/python-causality-handbook 在数据分析和决策科学领域&#xff0c;因果推断模型的评估是确保模型可靠性与实用性的…...

多模态融合避坑手册:为什么你的跨模态模型总掉进‘语义鸿沟’?

多模态融合避坑手册&#xff1a;为什么你的跨模态模型总掉进‘语义鸿沟’&#xff1f; 当你兴奋地将精心设计的跨模态模型投入训练&#xff0c;却发现验证集指标像过山车一样剧烈波动时&#xff0c;问题往往出在那些容易被忽视的工程细节里。上周有位工程师向我展示了他的视频…...

微信小程序蓝牙打印中文乱码?手把手教你GBK编码转换(附完整Demo)

微信小程序蓝牙打印中文乱码终极解决方案&#xff1a;从编码原理到完整实现 蓝牙打印机在零售、餐饮等行业的应用越来越广泛&#xff0c;而微信小程序作为轻量级应用平台&#xff0c;与蓝牙打印机的结合为商家提供了便捷的移动打印方案。但在实际开发中&#xff0c;开发者经常会…...

Unity开发HoloLens应用:从打包到安装的完整避坑指南(2024最新版)

Unity开发HoloLens应用&#xff1a;从打包到安装的完整避坑指南&#xff08;2024最新版&#xff09; 如果你正在尝试将Unity项目部署到HoloLens设备上&#xff0c;可能会遇到各种意想不到的问题。作为一位经历过无数次打包、部署、调试循环的开发者&#xff0c;我想分享一些实战…...

边缘计算中的存储挑战与解决方案

边缘计算中的存储挑战与解决方案 背景 作为一个专注于存储架构的技术人&#xff0c;我一直在关注边缘计算的发展。最近团队在部署边缘计算解决方案时&#xff0c;遇到了许多存储相关的挑战。为了帮助团队更好地理解和解决这些挑战&#xff0c;我决定写这篇实践指南。 边缘计算的…...

Mac Mouse Fix终极指南:让你的第三方鼠标在macOS上焕发新生

Mac Mouse Fix终极指南&#xff1a;让你的第三方鼠标在macOS上焕发新生 【免费下载链接】mac-mouse-fix Mac Mouse Fix - A simple way to make your mouse better. 项目地址: https://gitcode.com/GitHub_Trending/ma/mac-mouse-fix 还在为macOS上第三方鼠标功能受限而…...

MediaPipeUnityPlugin技术解构与实战指南:Unity AI视觉开发进阶之路

MediaPipeUnityPlugin技术解构与实战指南&#xff1a;Unity AI视觉开发进阶之路 【免费下载链接】MediaPipeUnityPlugin Unity plugin to run MediaPipe 项目地址: https://gitcode.com/gh_mirrors/me/MediaPipeUnityPlugin 问题发现&#xff1a;Unity AI视觉开发的现实…...

如何通过League-Toolkit智能工具提升英雄联盟操作效率

如何通过League-Toolkit智能工具提升英雄联盟操作效率 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 你是否曾因错过对局确认而被…...

Stable-Diffusion-V1-5 效率工具集:Ollama本地LLM辅助提示词生成

Stable-Diffusion-V1-5 效率工具集&#xff1a;Ollama本地LLM辅助提示词生成 你是不是也遇到过这种情况&#xff1a;脑子里有个绝妙的画面&#xff0c;但打开Stable Diffusion&#xff0c;面对那个空白的提示词输入框&#xff0c;却不知道从何写起。要么写得太简单&#xff0c…...