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

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

6.9-QT模拟计算器

源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...