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

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

news 来源：原创 2025/8/15 9:18:29

问题描述

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

河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就会下降 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

样例输出

样例说明

由于只有两块高度为 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;
}

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

问题描述小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就会下降 1 , 当石头的高度下降…...

编程日记 2025/8/15 9:18:29

uniapp+微信小程序+最简单局部下拉刷新实现

直接上代码 <scroll-view style"height: 27vh;" :scroll-top"scrollTop" scroll-y"true"scrolltolower"onScrollToLower1" lower-threshold"50"refresher-enabled"true" refresherrefresh"onRefresherR…...

编程日记 2025/8/15 9:18:29

Spring Boot 3.x 中 @NotNull 与 @NonNull 的深度解析

在 Java 开发领域，尤其是在 Spring Boot 生态系统中，空指针异常（NPEs）始终是一个顽固的挑战。这些运行时错误可能导致应用程序崩溃、数据不一致以及糟糕的用户体验。为了应对这一问题，Java 社区开发了各种空安全机制&a…...

编程日记 2025/8/15 9:18:28

SQLark 实战 | 如何从Excel、csv、txt等外部文件进行数据导入

数据导入导出是应用开发者在平时开发中最常用的操作之一，SQLark 里提供了方便的图形化界面来完成导入导出。本文先和大家分享如何从 Excel、csv、txt 等外部文件导入数据到数据库表中。 👉 前往 SQLark 官网：www.sqlark.com 下载全功能免费版…...

编程日记 2025/8/15 9:16:28

MATLAB中envelope函数使用

目录说明示例 chirp 的解析包络使用滤波器计算多通道信号的解析包络录音信号的移动 RMS 包络语音信号的峰值包络不对称序列的包络 envelope函数的功能是提取信号的包络。语法 [yupper,ylower] envelope(x) [yupper,ylower] envelope(x,fl,analytic) [yupper,…...

编程日记 2025/8/15 9:17:04

ES搭建详细指南+常见错误解决方法

Elasticsearch（ES）是一款开源的、分布式的、RESTful风格的搜索和数据分析引擎。它用于全文搜索、结构化搜索、分析等场景。以下是Elasticsearch的搭建步骤以及处理常见错误的方法。 Elasticsearch搭建步骤： 1.环境准备： 确保你的…...

编程日记 2025/8/15 9:16:28

Unity 封装一个依赖于MonoBehaviour的计时器(上) 基本功能

灵感来自下面这本书的协程部分,因此我就自己尝试写了一个我的新书Unity3D游戏开发（第3版） | 雨松MOMO程序研究院如果你不知道什么是协程:unity保姆级教程之协同程序_unity协同-CSDN博客一句话概括:协程就是单线程的异步操作,其作用于Unity的主线程 1…...

编程日记 2025/8/15 9:16:27

PostgreSQL数据库版本支持策略

PostgreSQL数据库版本支持策略主要版本会进行复杂的更改，因此无法以向后兼容的方式维护数据目录的内容。重大升级需要转储/重新加载数据库或使用pg_upgrade应用程序。我们还建议您阅读您计划升级到的主要版本的升级部分。您可以从一个主要版本升级到另一个&#xf…...

编程日记 2025/8/12 5:33:46

应用层之网络应用模型，HTTP/HTTPS协议

应用层是网络协议栈的最顶层，直接为应用程序提供通信服务，定义了不同主机间应用进程交互的规则，包括报文类型、语法、语义及通信时序一、网络应用模型 1.定义及特点模型定义核心特点典型应用场景C/S客户端向服务器发起请求，服…...

编程日记 2025/8/15 5:17:03

（七）Spring Boot学习——Redis使用

有部分内容是常用的，为了避免每次都查询数据库，将部分数据存入Redis。一、下载并安装 Redis Windows 版的 Redis 官方已不再维护，你可以使用微软提供的 Redis for Windows 版本或者使用 WSL（Windows Subsystem for Linux&a…...

编程日记 2025/8/15 9:17:03

11 | 给 Gin 服务器添加中间件

提示： 所有体系课见专栏：Go 项目开发极速入门实战课；欢迎加入云原生 AI 实战星球，12 高质量体系课、20 高质量实战项目助你在 AI 时代建立技术竞争力（聚焦于 Go、云原生、AI Infra）；本节课最终…...

编程日记 2025/8/14 9:20:19

selenium等待

通常代码执行的速度⽐页⾯渲染的速度要快，如果避免因为渲染过慢出现的⾃动化误报的问题呢？可以使⽤selenium中提供的三种等待⽅法： 1. 隐式等待（Implicit Wait）隐式等待适用于全局，它告诉 WebDriver 在查找元素时等待一定的时间，直到元素出现。如果超时，WebDriver 不…...

编程日记 2025/8/15 2:23:11

为什么List、Set集合无法在遍历的时候修改内部元素

以常用集合ArrayList为例，ArrayList 在遍历过程中无法直接修改内部元素的结构（例如通过 remove() 或 add() 方法修改元素），是因为遍历的过程中修改结构可能会导致不一致的行为、并发修改异常或逻辑错误。注意：和…...

编程日记 2025/8/14 10:42:06

使用 Elasticsearch 构建多模式 RAG 系统：哥谭市的故事

作者：来自 Elastic Alex Salgado 学习如何构建一个多模态检索增强生成 (RAG) 系统，该系统集成文本、音频、视频和图像数据，以提供更丰富的、具有上下文的信息检索。在这篇博客中，你将学习如何使用 Elasticsearch 构建一个多模态 …...

编程日记 2025/8/15 9:15:16

单一责任原则在Java设计模式中的深度解析

在软件开发中，设计模式提供了一种解决特定问题的思路。在众多的设计原则中，单一责任原则（Single Responsibility Principle，SRP）是一个非常重要的概念。它主要强调一个类应该只有一个责任，也就是说&#xf…...

编程日记 2025/8/14 10:44:41

设计模式学习记录

设计模式23种创建型抽象工厂模式工厂模式生成器模式原型模式单例模式结构型适配器模式桥接模式组合模式装饰模式外观模式享元模式代理模式行为型责任链模式命令模式解释器模式迭代器模式中介者模式备忘录模式观察者模式状态模式策略模式模版方法模式访问者模式创建型与对…...

编程日记 2025/8/15 9:15:14

set_clock_groups

一、命令参数与工具处理逻辑核心参数定义参数定义工具行为工具兼容性-asynchronous完全异步时钟组，无任何相位或频率关系（如独立晶振、不同时钟树）工具完全禁用组间路径的时序分析，但需用户自行处理跨时钟域（CDC&a…...

编程日记 2025/8/14 23:39:29

QT创建项目（项目模板、构建系统、选择类、构建套件）

1. 项目模版项目类型界面技术适用场景核心依赖模块开发语言Qt Widget ApplicationC Widgets传统桌面应用（复杂控件）Qt WidgetsCQt Console Application无 GUI命令行工具、服务Qt CoreCQt Quick ApplicationQML/Quick现代跨平台应用（动画/触…...

编程日记 2025/8/15 9:15:03

麒麟系统利用pycharm生成deb文件

在麒麟系统（Kylin OS）上使用 PyCharm 进行 Python 开发并生成 .deb 可安装软件包，可以按照以下步骤进行操作： 1. 准备工作安装 PyCharm：确保已经在麒麟系统上安装了 PyCharm，可以使用官方提供的安装包进…...

编程日记 2025/8/15 9:15:15

超声重建，3D重建超声三维重建，三维可视化平台 UR 3D Reconstruction

1. 超声波3D重建技术的实现方法与算法技术概述 3D超声重建是一种基于2D超声图像生成3D体积数据的技术，广泛应用于医学影像领域。通过重建和可视化三维结构，3D超声能够显著提高诊断精度和效率，同时减少医生的脑力负担。本技术文档将详细阐述…...

编程日记 2025/8/15 9:15:16

Qt 信号与槽

目录 Qt信号和槽 connect函数 connect使用方法自定义信号与自定义槽 Qt界面化工具自动生成的槽自定义信号带参数的信号和槽信号与槽的断开 Qt信号和槽谈到信号，设计3个要素信号源：谁发出了信号信号触发条件：哪个控件的哪个…...

编程日记 2025/8/15 9:13:16

卷积神经网络 - 卷积的变种、数学性质

本文我们来学习卷积的变种和相关的数学性质，为后面学习卷积神经网络做准备，有些概念可能不好理解，可以先了解其概念，然后慢慢理解、逐步深入。在卷积的标准定义基础上，还可以引入卷积核的滑动步长和零填充来增加卷积…...

编程日记 2025/8/15 9:15:16

ubuntu 和 RV1126 交叉编译Mosqutiio-1.6.9

最近需要交叉编译mosquitto，遇到一些小问题记录一下。 1.众所周知使用它自带的Makefile编译的时候，只需要在编译前，指定它config.mk中的变量：CFLAGS头文件路径和 LDFLAGS库文件路径就ok，例子如下： expor…...

编程日记 2025/8/15 9:12:22

从零开始学习机器人---如何高效学习机械原理

如何高效学习机械原理 1. 理解课程的核心概念2. 结合图形和模型学习3. 掌握公式和计算方法4. 理论与实践相结合5. 总结和复习6. 保持好奇心和探索精神总结机械原理是一门理论性和实践性都很强的课程，涉及到机械系统的运动、动力传递、机构设计等内容。快速学习机械…...

编程日记 2025/7/17 9:06:55

STM32 RS232通信开发全解析 | 零基础入门STM32第五十九步

主题内容教学目的/扩展视频RS232串口电路原理，跳线设置，驱动程序。与超级终端通信。了解电路原理和RS232协议。师从洋桃电子，杜洋老师 📑文章目录一、RS232通信系统架构二、RS232核心原理与硬件设计2.1 电气特性对比2.2 典型电路…...

编程日记 2025/8/13 11:23:14

文献分享: 对ColBERT段落多向量的剪枝——基于学习的方法

原论文 1. 导论 & \textbf{\&} &方法 1️⃣要干啥：在 ColBERT \text{ColBERT} ColBERT方法中，限制每个段落要保留的 Token \text{Token} Token的数量，或者说对段落 Token \text{Token} Token进行剪枝 2️⃣怎么干：注…...

编程日记 2025/8/10 10:08:41

(已解决)aws 上部署Splunk 负载均衡unhealthy

在AWS 部署Splunk 服务，instance 是后端的EC2, 我把splunk 服务起好后，发现port : 8000 是listening: #netstat -an | grep 80 tcp 0 0 127.0.0.1:8065 0.0.0.0:* LISTEN tcp 0 0 0.0.0.0:8089 0.0.0.0:* …...

编程日记 2025/8/12 7:02:06

C# 异步编程

概述同步：指必须等待前一个操作完成，后续操作才能继续。同步操作会阻塞线程直到任务完成。异步：异步操作不会阻塞线程，允许程序在等待某个任务完成的同时，继续执行其他任务。异步编程适用场景： 1、从…...

编程日记 2025/8/10 3:41:52

缓存之美：Guava Cache 相比于 Caffeine 差在哪里？

大家好，我是方圆。本文将结合 Guava Cache 的源码来分析它的实现原理，并阐述它相比于 Caffeine Cache 在性能上的劣势。为了让大家对 Guava Cache 理解起来更容易，我们还是在开篇介绍它的原理： Guava Cache 通过分段（…...

编程日记 2025/8/14 7:49:58

Go string 字符串底层逻辑

在 Go 语言中，string 类型的底层结构是一个结构体，包含两个字段：一个指向字节数组的指针和该字节数组的长度。以下是其在 Go 源码中的大致定义：type stringStruct struct {str unsafe.Pointerlen int } str：这是一个指…...

编程日记 2025/8/8 4:45:57

高效集成聚水潭采购退货数据到MySQL的最佳实践

聚水潭数据集成到MySQL：采购退货单的高效对接方案在企业的数据管理和分析过程中，数据的准确性和实时性至关重要。本文将分享一个具体的系统对接集成案例：如何通过轻易云数据集成平台，将聚水潭中的采购退货单数据高效地集成到MyS…...

编程日记 2025/8/10 14:50:35

STM32步进电机S型与T型加减速算法

目录一、基本原理二、常见类型三、算法详解四、应用场合五、代码实现 1、main...

编程日记 2025/7/13 11:26:17

centos操作系统上传和下载百度网盘内容

探序基因整理进入百度网盘官网百度网盘客户端下载下载linux的rpm格式的安装包在linux命令行中输入：rpm -ivh baidunetdisk_4.17.7_x86_64.rpm 出现报错： 错误：依赖检测失败： libXScrnSaver 被 baidunetdisk-4.17.7-1.x8…...

编程日记 2025/8/14 12:58:59

深入 Python 网络爬虫开发：从入门到实战

一、为什么需要爬虫？ 在数据驱动的时代，网络爬虫是获取公开数据的重要工具。它可以帮助我们： 监控电商价格变化抓取学术文献构建数据分析样本自动化信息收集二、基础环境搭建 1. 核心库安装 pip install requests beautifulsoup4 lxml …...

编程日记 2025/8/11 12:01:09

网络爬虫【简介】

我叫补三补四，很高兴见到大家，欢迎一起学习交流和进步今天来讲一讲爬虫一、网络爬虫的定义网络爬虫（Web Crawler），又称为网络蜘蛛、网络机器人等，是一种按照一定规则自动抓取互联网信息的程序或脚本。它…...

编程日记 2025/8/8 16:54:17

Linux：Ubuntu server 24.02 上搭建 ollama + dify

一、安装Ubuntu 具体的安装过程可以参见此链接：链接：Ubuntu Server 20.04详细安装教程，这里主要记录一下过程中遇到的问题。安装时subnet如何填写在Ubuntu中subnet填写255.255.255.0是错误的，其格式为 xx.xx.xx.xx/yy &#…...

编程日记 2025/8/12 7:51:05

题目分析代码 #include <bits/stdc.h> using namespace std;const int N 24; const int inf 0x3f3f3f3f;int mins[N], minv[N]; int R[N], H[N]; int n, m, ans inf;void dfs(int u, int v, int s) {if(v minv[u] > n) return;if(s mins[u] > ans) return;…...

编程日记 2025/8/13 10:51:08

RabbitMq C++客户端的使用

1.RabbitMq介绍 RabbitMQ 是一款开源的消息队列中间件，基于 AMQP（高级消息队列协议）实现，支持多种编程语言和平台。以下是其核心特点和介绍： 核心特点多语言支持提供 Java、Python、C#、Go、JavaScript 等语言的客…...

编程日记 2025/8/13 9:48:03

入门基础项目-前端Vue_02

文章目录 1. 用户信息1.1 整体设计1.2 完整代码 User.vue1.2.1 数据加载1.2.2 表格 el-table1.2.2.1 多选1.2.2.2 自定义列的内容 Slot1.2.2.3 图片 el-image1.2.2.4 分页 el-pagination 1.2.3 编辑1.2.3.1 弹出框 el-dialog1.2.3.2 上传 el-upload 1.2.4 新增1.2.5 删除1.2.6 …...

编程日记 2025/8/12 17:49:09

C#中SerialPort 的使用

最近在学习C#的SerialPort ，关于SerialPort 的使用，做如下总结： 1.可以通过函数System.IO.Ports.SerialPort.GetPortNames() 将获得系统所有的串口名称。C#代码如下： string[] sPorts SerialPort.GetPortNames(); foreach(stri…...

编程日记 2025/8/15 5:13:13

使用py-ffmpeg批量合成视频的脚本

我有一个小米摄像头，用它录出来的视频全部都是3s一段3s一段的。其中有几个小时的视频我需要保存，当初直接把摄像头的卡文件导出来重命名掉了，那时候没有注意，之后想剪辑/发送给别人的时候发现疯了： 1.剪辑的话&#x…...

编程日记 2025/8/11 13:48:54

mac安装navicat及使用

0.删除旧的 sudo rm -Rf /Applications/Navicat\ Premium.app sudo rm -Rf /private/var/db/BootCaches/CB6F12B3-2C14-461E-B5A7-A8621B7FF130/app.com.prect.NavicatPremium.playlist sudo rm -Rf ~/Library/Caches/com.apple.helpd/SDMHelpData/Other/English/HelpSDMIndexF…...

编程日记 2025/8/7 16:10:26

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

相关文章：