蓝桥杯备赛-二分-青蛙过河

问题描述

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。

河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上(某次跳跃 后使石头高度下降到 0 是允许的)。

小青蛙一共需要去学校上 xx 天课, 所以它需要往返 2x2x 次。当小青蛙具有 一个跳跃能力 yy 时, 它能跳不超过 yy 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 xx 次课。

输入格式

输入的第一行包含两个整数 n,xn,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x2x 才是实际过河的次数。

第二行包含 n−1n−1 个非负整数 H1,H2,⋯,Hn−1H1​,H2​,⋯,Hn−1​, 其中 Hi>0Hi​>0 表示在河中与 小青蛙的家相距 ii 的地方有一块高度为 HiHi​ 的石头, Hi=0Hi​=0 表示这个位置没有石 头。

输出格式

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

样例输入

5 1
1 0 1 0

样例输出

4

样例说明

由于只有两块高度为 11 的石头,所以往返只能各用一块。第 11 块石头和对岸的距离为 44,如果小青蛙的跳跃能力为 33 则无法满足要求。所以小青蛙最少需要 44 的跳跃能力。

评测用例规模与约定

对于 30%30% 的评测用例, n≤100n≤100;

对于 60%60% 的评测用例, n≤1000n≤1000;

对于所有评测用例, 1≤n≤105,1≤x≤109,1≤Hi≤1041≤n≤105,1≤x≤109,1≤Hi​≤104 。

#include<iostream>
#include<vector>
using namespace std;
int n, x;
vector<int> h(1000000,0);
vector<int> sum(1000000, 0);//前缀和便于计算区间和
//本题思路很简单,假设跳跃值看能不能满足条件
//重点是如何判断是否成功?
/*假设此刻jump为3
岸,1,2,3,|4,5,6,|7,8,9,岸
从起始岸蹦一步/两步/三步分别到1,2,3
所以第一跳一定在1,2,3,任意一个之间,所以1,2,3高度和要>=2x
在1时,下一步只能走到4去,因此,想要容纳1全部的被踩次数,4号的石头高度应>=1号,[1,3]总高度>=2x,
又因4号高度>=1号高度,故区间[2,4]高度之和>=2x,以此类推.
可以证明,要想总过河次数>=2x,任一石头编号i开始,长度为步长的区间[i,i+步长-1]石头总高度之和>=2x
*/
bool check(int j) {for (int i = 1; i <= n-j; i++) {//一共n-1个石头,不是n个,所以是n-1-j+1=n-jint count = sum[i + j - 1] - sum[i - 1];if (count < 2 * x) return false;}return true;
}
int main()
{cin >> n >> x;for (int i = 1; i <= n - 1; i++) {cin >> h[i];sum[i] = sum[i - 1] + h[i];}int l = 1;int r = n;while (l < r) {int middle = (l + r) / 2;if (check(middle)) {r = middle;}else {l = middle + 1;}}cout << l;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34167.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

《计算机图形学》第二课笔记-----二维变换的推导

前言&#xff1a;为什么这么突兀的把这一节内容放在了第二课&#xff0c;第一是因为我急于求成&#xff0c;第二是因为这一章节太重要了&#xff0c;这几乎是二维三维变换的最核心的东西&#xff0c;理解了这一章节内容&#xff0c;后面的就会像打通了任督二脉一样&#xff0c;…

OTP单片机调试工具之—单线数据编码

OTP单片机调试工具在实现过程中离不开单线数据的传输&#xff0c;那么使用哪一种方式的数据编码会比较好呢&#xff1f; 我所了解的主要有以下三种&#xff1a; 1.UART&#xff08;串口&#xff09;&#xff0c;这种方式在单片机和pc之间进行传输都非常常见&#xff0c;效率比较…

背诵--2

DAY01 面向对象回顾、继承、抽象类 学习目标 能够写出类的继承格式public class 子类 extends 父类{}public class Cat extends Animal{} 能够说出继承的特点子类继承父类,就会自动拥有父类非私有的成员 能够说出子类调用父类的成员特点1.子类有使用子类自己的2.子类没有使用…

穷举vs暴搜vs深搜vs回溯vs剪枝刷题 + 总结

文章目录 全排列题解代码 子集题解代码 总结 全排列 题目链接 题解 1. 画一颗决策树 2. 全局变量&#xff1a; int[ ][ ] ret&#xff1a;用于存结果的二维数组 int[ ] path&#xff1a;用于存每次路径的答案 bool[ ] check&#xff1a;判断这个数是否已经用过&#xff0c;…

深度学习中学习率调整策略

学习率衰减策略是深度学习优化过程中的一个关键因素&#xff0c;它决定了训练过程中学习率的调整方式&#xff0c;从而影响模型收敛的速度和效果。不同的衰减策略在不同的任务和模型上可能有不同的表现&#xff0c;下面从我用到过的几个衰减策略进行记录&#xff0c;后续慢慢跟…

《Electron 学习之旅:从入门到实践》

前言 Electron 简介 Electron 是由 GitHub 开发的一个开源框架&#xff0c;基于 Chromium 和 Node.js。 它允许开发者使用 Web 技术&#xff08;HTML、CSS、JavaScript&#xff09;构建跨平台的桌面应用程序。 Electron 的优势 跨平台&#xff1a;支持 Windows、macOS 和 Linux…

UBuntu24.04-JDK7-TOMCAT7安装

jdk7 apt-get 找不到。 tomcat7 也没找到。 以下是安装成功的&#xff0c;供大家参考。 1.JAVA openjdk-7-jdk /usr/lib/jvm/java-7-openjdk-amd641.安装指定版本apt search jdk //查找版本sudo apt install default-jdk //此为默认版本sudo apt install ope…

美畅物联丨WebRTC 技术详解:构建实时通信的数字桥梁

在互联网技术飞速发展的今天&#xff0c;实时通信已成为数字生活的核心需求。WebRTC作为一个开源项目&#xff0c;凭借卓越的技术实力与创新理念&#xff0c;为网页和移动应用带来了颠覆性的实时通信能力。它突破了传统通信方式的限制&#xff0c;实现了音频、视频和数据在用户…

驾驭 DeepSeek 科技之翼,翱翔现代学习新天际

在当今这个信息爆炸的时代&#xff0c;学习的方式和途径正在经历着前所未有的变革。人工智能技术的飞速发展&#xff0c;为我们的学习带来了全新的机遇和挑战。DeepSeek 作为一款强大的大语言模型&#xff0c;凭借其卓越的性能和丰富的功能&#xff0c;为现代学习注入了新的活力…

写时拷贝技术

目录 写时拷贝 核心思想 基本原理 基本过程 一个例子深入理解 补充知识--引用计数 小总结 写时拷贝实现 宏观理解&#xff08;进程、线程角度&#xff09; 资源共享 只读访问 写操作触发拷贝 独立修改 微观理解&#xff08;fork系统调用角度&#xff09; 进程创…

requests库的request和response对象的属性和方法

Python requests库 request 参数信息 response 参数信息

MySQL数据库操作

目录 SQL语句 1、SQL的背景 2、SQL的概念 SQL的分类 SQL的书写规范 MySQL数据库 1、MySQL数据库的编码 &#xff08;1&#xff09;utf8和utf8mb4的区别 &#xff08;2&#xff09;MySQL的字符集 &#xff08;3&#xff09;MySQL默认编码为 latin1 &#xff0c;如何更改…

Blender-MCP服务源码5-BlenderSocket插件安装

Blender-MCP服务源码5-BlenderSocket插件安装 上一篇讲述了Blender是基于Socket进行本地和远程进行通讯&#xff0c;现在尝试将BlenderSocket插件安装到Blender中进行功能调试 1-核心知识点 将开发的BlenderSocket插件安装到Blender中 2-思路整理 1&#xff09;将SocketServe…

Androidstudio实现一个app引导页(超详细)

文章目录 1. 功能需求2. 代码实现过程1. 创建布局文件2. 创建引导页的Adapter3. 实现引导页Activity4. 创建圆点指示器的Drawable5. 创建“立即体验”按钮的圆角背景 2.效果图 1. 功能需求 1、需要和原型图设计稿对应的元素保持一致的样式。 2、引导页需要隐藏导航栏&#xff…

蓝桥杯省赛真题C++B组-小球反弹

一、题目 有一长方形&#xff0c;长为 343720 单位长度&#xff0c;宽为 233333 单位长度。在其内部左上角顶点有一小球(无视其体积)&#xff0c;其初速度如图所示且保持运动速率不变&#xff0c;分解到长宽两个方向上的速率之比为 dx:dy 15:17。小球碰到长方形的边框时会发生…

基于深度学习的多模态人脸情绪识别研究与实现(视频+图像+语音)

这是一个结合图像和音频的情绪识别系统&#xff0c;从架构、数据准备、模型实现、训练等。包括数据收集、预处理、模型训练、融合方法、部署优化等全流程。确定完整系统的组成部分&#xff1a;数据收集与处理、模型设计与训练、多模态融合、系统集成、部署优化、用户界面等。详…

AI 数字人短视频源码开发:开启虚拟世界的创意引擎

在当今数字化浪潮中&#xff0c;AI 数字人正以惊人的速度融入我们的生活&#xff0c;尤其是在短视频领域&#xff0c;AI 数字人凭借其独特的魅力吸引了无数目光。从虚拟偶像的舞台表演到智能客服的贴心服务&#xff0c;AI 数字人已成为推动短视频行业创新发展的重要力量。而这背…

Java 代理模式:从静态代理到动态代理

前言 代理模式是 Java 中常见的设计模式之一&#xff0c;它的核心思想是通过一个代理对象来控制对真实对象的访问。代理模式不仅可以扩展目标对象的功能&#xff0c;而且在不修改原目标对象的情况下&#xff0c;可以增加一些我们自定义的操作。 1. 代理模式简介 代理模式的核心…

PyCharm 2019.1.3使用python3.9创建虚拟环境setuptools-40.8.0报错处理

目录 前置&#xff1a; 一劳永逸方法&#xff08;缺最后一步&#xff0c;没有成行&#xff09; step one: 下载高版本的pip、setuptools、virtualenv的tar.gz包 step two: 进入PyCharm安装目录的 helpers 目录下 step three: 下载并安装grep和sed命令&#xff0c;然后执行 …

word处理控件Aspose.Words教程:使用 Python 删除 Word 中的空白页

Aspose.Words 是一种高级Word文档处理API&#xff0c;用于执行各种文档管理和操作任务。API支持生成&#xff0c;修改&#xff0c;转换&#xff0c;呈现和打印文档&#xff0c;而无需在跨平台应用程序中直接使用Microsoft Word。 Aspose API支持流行文件格式处理&#xff0c;并…