当前位置: 首页 > 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;成为自己想成为…...

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

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

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...