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

问题 B: 跳石头(C++)(二分答案)

目录

1.题目描述

2.AC


1.题目描述

问题 B: 跳石头

时间限制: 1.000 Sec  内存限制: 128 MB
提交 状态

题目描述

一年一度的“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有N块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M块岩石(不能移走起点和终点的岩石)。

输入

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

输出

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

样例输入 Copy

25 5 2
2
11
14
17 
21

样例输出 Copy

4

提示

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

对于 20% 的数据,0≤M≤N≤10。
对于 50% 的数据,0≤M≤N≤100。
对于 100% 的数据,0≤M≤N≤50,000,1≤L≤1,000,000,000。

2.AC

#include <iostream>
#include <cstdio>
using namespace std;
int l, n, m, ans;
int a[50005];
int check(int x) {int p = 0, cnt = 0;for (int i = 1; i <= n+1; i++) {if (a[i]-p < x) cnt++;else p = a[i];}if (cnt>m) return 0;return 1;
}
int main () {scanf("%d%d%d", &l, &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}a[n+1] = l;int le = 0, ri = l;while (le <= ri) {int mid = le + (ri - le) / 2;if (check(mid)) le = mid + 1, ans = mid;else ri = mid - 1;}cout<<ans;return 0;
}

相关文章:

问题 B: 跳石头(C++)(二分答案)

目录 1.题目描述 2.AC 1.题目描述 问题 B: 跳石头 时间限制: 1.000 Sec 内存限制: 128 MB提交 状态 题目描述 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点…...

bugku——变量1

拿到题目后是一串PHP代码&#xff0c;给到提示是flag在变量中&#xff0c;接下来进行代码审计 error_reporting(0)&#xff1a;关闭错误报告 include “flag1.php”:包含flag1.php文件 highlight_file(_file_)&#xff1a;页面进行语法高亮显示 isset($_GET[‘args’])&#xf…...

网络数据包丢失监控

什么是网络数据包 数据包或网络数据包是通过网络传输的小数据单元。顾名思义&#xff0c;这些是小的、离散的数据单元。单独来看&#xff0c;这些单位不一定有多大意义。它们只是正在传输的整体消息的一部分&#xff0c;这些消息已被组装成多个层。但是&#xff0c;当组合在一…...

Linux服务器安装部署MongoDB数据库 - 无公网IP远程连接

目录 前言 1. 配置Mongodb源 2. 安装MongoDB 3. 局域网连接测试 4. 安装cpolar内网穿透 5. 配置公网访问地址 6. 公网远程连接 7. 固定连接公网地址 8. 使用固定地址连接 转载自Cpolar Lisa文章&#xff1a;Linux服务器安装部署MongoDB数据库 - 无公网IP远程连接「内网…...

CSS面试题:30道含答案和代码示例的练习题

什么是 CSS&#xff1f;它的作用是什么&#xff1f; CSS&#xff08;层叠样式表&#xff09;是一种用于描述网页样式的语言。它的作用是控制网页的布局、字体、颜色、背景等方面的样式。如何在 HTML 页面中引入 CSS&#xff1f; 可以使用 标签将 CSS 文件引入到 HTML 页面中。例…...

时间轮的golang实践浅析

引言 下列代码模仿一段RPC请求的执行过程&#xff0c;执行后会有哪些问题&#xff1a; RPC代码示例答案&#xff1a;因为超时控制后未阻断后续请求&#xff0c;导致并发读写产生Panic思考&#xff1a;客户端发起 HTTP 请求后&#xff0c;如果在指定时间内没有收到服务器的响应…...

Linux命令_stress 快速模拟CPU、内存、磁盘消耗

ping的安装命令&#xff1a;apt-get install -y inetutils-ping 会遇到Unable to locate package inetutils-ping问题 正确的操作是&#xff1a; ** 这时候需要敲&#xff1a;apt-get update&#xff0c;这个命令的作用是&#xff1a;同步 /etc/apt/sources.list 和 /etc/apt/…...

可视化绘图技巧100篇分析篇(二)-生存曲线(LM曲线)

目录 前言 几个高频面试题目 roc曲线和生存曲线区别 生存曲线模型 生存曲线组件讲解...

UP主发车啦!撩人仙侠文系列,谁来管管这个反派啊!

本人书龄4年&#xff0c;平时很爱看小说&#xff0c;阅遍无数经典修仙文&#xff0c;熬夜党的最爱啊&#xff01;&#xff01;&#xff01;&#xff01;我心中的仙侠top&#xff0c;都是我的心头爱。 一般我都会跟朋友说这六本五星级仙侠好文&#xff0c;如果她们不看&#xf…...

K8S使用持久化卷存储到NFS(NAS盘)

参考文章&#xff1a;K8S-v1.20中使用PVC持久卷 - 知乎 目录 1、概念&#xff1a; 1.1 基础概念 1.2 PV的配置 1.2.1 静态PV配置 1.2.2 动态PV配置 1.2.3 PVC与PV的绑定 1.2.4 PVC及PV的使用 2 部署PV及PVC 2.1 所有K8S机器都需要安装NFS程序 2.2 仅针对需要暴露文件…...

一图看懂 multidict 模块:类似于字典的键值对集合,键可以多次出现,资料整理+笔记(大全)

本文由 大侠(AhcaoZhu)原创&#xff0c;转载请声明。 链接: https://blog.csdn.net/Ahcao2008 一图看懂 multidict 模块&#xff1a;类似于字典的键值对集合&#xff0c;键可以多次出现&#xff0c;资料整理笔记&#xff08;大全&#xff09; &#x1f9ca;摘要&#x1f9ca;模…...

django CBV 与 DRF APIView源码分析

django CBV源码分析 在django框架中&#xff0c;视图层中的逻辑即可以使用函数处理也可以使用类进行处理&#xff0c;如果在视图层中使用函数处理请求&#xff0c;就是FBV(function base views)&#xff0c;如果在视图层中使用类处理请求&#xff0c;就是CBV(class base views…...

沃尔玛入驻教程:中国卖家如何免费、快速入驻沃尔玛walmart.com?

作为一家全球知名的零售巨头&#xff0c;沃尔玛&#xff08;Walmart&#xff09;的在线商城walmart.com拥有庞大的消费者基础和巨大的商机。对于中国的卖家来说&#xff0c;入驻沃尔玛的平台是一个很好的机会&#xff0c;但是有没有什么方法可以免费、快速入驻呢&#xff1f;有…...

《花雕学AI》Poe 上的四种 AI 机器人,你该怎么选?ChatGPT、Sage、Claude 和 Dragonfly对比

虽然 ChatGPT 是一项革命性的技术&#xff0c;但它作为一个消费产品却有点失败。你可能会花很长时间等待 OpenAI 的聊天机器人加载&#xff0c;或者根本无法使用它&#xff0c;因为它太大了。就算你能用上它&#xff0c;它也很缓慢&#xff0c;而且它的界面也很丑陋。它甚至没有…...

localStorage

目录 localStorage与sessionStorage localStorage的Set与Get localStorage传递参数 localStorage与sessionStorage 现代浏览器提供了一种被称为"Web Storage APIs"&#xff08;Web 存储接口&#xff09;的机制&#xff0c;允许在同一浏览器的不同标签页之间共享数…...

二十五、SQL 数据分析实战(9个中等难度的SQL题目)

文章目录 题目1: App 使用频率分析题目2: App 下载情况统计题目3: 寻找活跃学习者题目4: 商品分类整理题目5: 商品销售分析题目6: 网约车司机收益统计题目7: 网站登录时间间隔统计题目8: 不同区域商品收入统计题目9: 信贷逾期情况统计 题目1: App 使用频率分析 现有一张用户使…...

JavaSE_02基本语法-编程单词词汇

boolean [bʊlɪən] 变量的基本数据类型之一&#xff1a;布尔型const [kɒnst] n. 常量&#xff0c;常数constant [kɒnst(ə)nt] n. [数] 常数&#xff1b;恒量continue [kən’tɪnjuː] vi. 继续&#xff0c;连续;default [dɪ’fɔːlt; diːfɔːlt] 默认的&#xff0c;缺…...

区间预测 | MATLAB实现QRDNN深度神经网络分位数回归时间序列区间预测

区间预测 | MATLAB实现QRDNN深度神经网络分位数回归时间序列区间预测 目录 区间预测 | MATLAB实现QRDNN深度神经网络分位数回归时间序列区间预测效果一览基本介绍模型描述程序设计参考资料 效果一览 基本介绍 MATLAB实现QRDNN深度神经网络分位数回归时间序列区间预测。QRDNN模型…...

如何使用aframe.js构建一个简单的VR播放器

在当今这个信息化的时代&#xff0c;虚拟现实&#xff08;VR&#xff09;已经开始逐渐成为一种新的生活方式。作为一名前端开发工程师&#xff0c;在学习和探索VR技术方面&#xff0c;aframe.js是一个非常有趣和有用的工具。在本文中&#xff0c;我将介绍如何使用aframe.js构建…...

Fiddler抓包工具常见功能介绍,还不会的进来看

目录 Fiddler的功能面板 一、Statistics数据统计面板&#xff0c;性能分析 二、Inspectors查看请求与响应 三、Filters过滤器 1、User Filters启用 2、Action 3、过滤器实际应用 四、AutoResponder请求重定向 1、什么是请求重定向&#xff1f; 2、为什么要用这个功能&…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...