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

P8775 [蓝桥杯 2022 省 A] 青蛙过河

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1

5 1
1 0 1 0

输出 #1

4

说明/提示

【样例解释】

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

【评测用例规模与约定】

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

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

对于所有评测用例,1≤n≤10^{5},1≤x≤10^{9},0≤Hi≤10^{4}

蓝桥杯 2022 省赛 A 组 F 题。

题目解析

一条河,河里有些石头,小青蛙要上x天学,也就说他要从湖面上经过2x次,在石头起跳会使石头高度降低1,高度为0时不能经过,现在要求他跳跃能力最小是多少(在跳跃能力内的石头他都能跳到)

解题方法

看到这题我们想到最简单的方法就是枚举,但很显然数据并不允许,那么我们就得考虑优化枚举(做题时,可以先考虑枚举的做法,在考虑如何优化),这道题很显然可以用二分优化,大家就看,二分跳跃能力,中间值跳不过去,那就找比较大的那块区域,跳过去了,就考虑比较小的那块区域,看看有没有更小的。而在求可不可以跳过去那块,只需要用前缀和维护一下就可以了(前缀和判断区域内是否有落脚点)

代码

理解了最重要,这里放上ACcode,如果你是为这个而来的,那么恭喜你,你做了一定跟没做一样。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,a[100001],qzh[100001];
bool checker(int mid){
	for(int i=mid;i<n;i++){
		if(qzh[i]-qzh[i-mid]<2*x){
			return 0;
		}
	}
	return 1;
}
signed main(){
	scanf("%lld%lld",&n,&x);
	for(int i=1;i<=n-1;i++){
		scanf("%lld",&a[i]);
		qzh[i]=qzh[i-1]+a[i];
	}
	int left=1,right=n;
	while(left<right){
		int mid=(right+left)/2;
		if(checker(mid))right=mid;
		else left=mid+1;
	}
	printf("%lld",left);
} 

讲完了,希望大家能够理解

留个赞关个注再走呗qwq


http://www.kler.cn/a/372591.html

相关文章:

  • Docker Compose一键部署Spring Boot + Vue项目
  • 复现第一周24
  • 书生实战营第四期-第三关 Git+InternStudio
  • 第5章 中级控件
  • 深入理解gPTP时间同步过程
  • Redmi Note 12 Turbo 1TB root教程
  • CUDA环境安装终极指南——Linux(其它系统也一样)
  • 订购 Claude AI 的第二天 它独自完成 文字转语音 flask应用
  • C++ | Leetcode C++题解之第519题随机翻转矩阵
  • 轻型民用无人驾驶航空器安全操控理论培训知识总结-多旋翼部分
  • Redis 下载安装(Windows11)
  • 算法刷题基础知识总结
  • 逆变器前级倍压方案【工作日志】
  • 未来生活中的AI电脑是怎样的
  • 2023 春季测试 题解
  • 论坛系统测试报告
  • Postgresql源码(137)执行器参数传递与使用
  • 大语言模型(LLM)快速理解
  • DOM---鼠标事件类型(移入移出)
  • 基于Unet卷积神经网络的脑肿瘤MRI分割
  • LinkedList和链表(下)
  • 豆包,攻克数字是个什么工具?《GKData-挖掘数据的无限可能》(数据爬虫采集工具)
  • Ceph 存储系统全解
  • TMUX1308PWR规格书 数据手册 具有注入电流控制功能的 5V 双向 8:1单通道和 4:1 双通道多路复用器芯片
  • Android平台RTSP|RTMP播放器高效率如何回调YUV或RGB数据?
  • asp.net core 跨域配置不起作用的原因