二分答案 蓝桥杯 2022 省A 青蛙过河

有些地方需要解释:
1.从学校到家和从家到学校,跳跃都是一样的,直接看作2*x次过河就可以。        
2.对于一个跳跃能力 y,青蛙能跳过河 2x 次,当且仅当对于每个长度为 y 的区间,这个区间内 h 的和都大于等于 2x。

思路分析

  1. 首先定义了一个辅助函数 check,用于检查是否存在一种跳跃能力满足要求。该函数接受三个参数:跳跃能力 x、石头高度数组 arr 和总共需要跳跃的距离 all
  2. 主函数开始时,读入河的宽度 n 和小青蛙需要去学校的天数 x,并将 x 转换为实际过河的次数。
  3. 接着读入每块石头的高度,并初始化二分查找的左右边界。
  4. 使用二分查找来找到最低的跳跃能力,使得小青蛙能够按要求过河。二分查找的左边界为1,右边界为 n-1
  5. 在二分查找的过程中,调用 check 函数检查当前跳跃能力是否满足要求,如果满足则更新最低跳跃能力,并将右边界调整为 mid-1,否则将左边界调整为 mid+1
  6. 最终输出最低跳跃能力。
#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int n;//河的长度

// 辅助函数:检查是否存在一种跳跃能力满足要求
int check(int x, int arr[], int all) {
    int now = 0; // 初始化小青蛙的位置
    // 模拟小青蛙的跳跃过程
    for(int i = 0; i < x; i++) {
        now += arr[i]; // 跳到下一个石头或河岸上
    }
    // 如果小青蛙无法跳到河的对岸,返回0
    if(now < all)
        return 0;
    // 继续模拟小青蛙的跳跃,判断是否能成功到达河的对岸
    for(int i = x; i < n; i++) {
        now += arr[i]; // 跳到下一个石头或河岸上
        now -= arr[i - x]; // 减去前一个石头的高度,保持距离为x
        if(now < all) // 如果无法成功到达河的对岸,返回0
            return 0;
    }
    // 能够成功到达河的对岸,返回1
    return 1;
}

int main() {
    int x;
    cin >> n >> x; // 读取河的宽度和小青蛙需要去学校的天数
    x *= 2; // 实际过河的次数为2倍天数
    int arr[n];
    for(int i = 0; i < n - 1; i++) // 读取每块石头的高度
        cin >> arr[i];
    int mid, ans = n;
    int left = 1, right = n; // 初始跳跃能力范围为[1, n]
    n = n - 1; // 更新河的宽度为石头数量
    // 使用二分查找来找到最低的跳跃能力,使得小青蛙能够按要求过河
    while(left <= right) {
        mid = (left + right) / 2;
        if(check(mid, arr, x) == 1) {
            ans = mid; // 更新最低跳跃能力
            right = mid - 1;
        } else
            left = mid + 1;
    }
    // 输出最低跳跃能力
    cout << ans;
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一文彻底搞懂synchronized实现原理

文章目录 1. synchronized 是什么2. synchronized 可以实现的锁3. synchronized 使用4. synchronized 底层原理4.1 作用于同步代码块4.2 作用于方法 1. synchronized 是什么 synchronized 是 Java 中实现线程同步的关键字&#xff0c;用于保护共享资源的访问&#xff0c;确保在…

TCP/IP协议、HTTP协议和FTP协议等网络协议包简介

文章目录 一、常见的网络协议二、TCP/IP协议1、TCP/IP协议模型被划分为四个层次2、TCP/IP五层模型3、TCP/IP七层模型 三、FTP网络协议四、Http网络协议1、Http网络协议简介2、Http网络协议的内容3、HTTP请求协议包组成4、HTTP响应协议包组成 一、常见的网络协议 常见的网络协议…

如何打包一个手机软件

目录 前言&#xff1a; 准备工具&#xff1a; 创建项目&#xff1a; 打包程序&#xff1a; 前言&#xff1a; 我们平时手机上使用的程序&#xff0c;或者电脑上使用的程序都可以由Web程序打包而来的&#xff0c;而打包不是一个.html文件也不是一个.js文件而是一个大型的文…

【AAOS车载系统+AOSP14系统攻城狮入门实战课】:正式上线了(二百零三)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

Blender怎么样启动默认移动和Cavity效果

在使用Blender的过程中&#xff0c;有一些特殊的技巧很重要。 比如默认地设置blender打开时&#xff0c;就是移动物体&#xff0c;这样怎么样设置的呢&#xff1f; 需要在界面里打开下面的菜单: 这样就找到默认设置的地方&#xff0c;把下面的移动勾选起来&#xff0c;这样点…

使用注意力机制的 LSTM 彻底改变时间序列预测

目录 一、说明二、LSTM 和注意力机制简介三、为什么要将 LSTM 与时间序列注意力相结合&#xff1f;四、模型架构训练与评估 五、验证六、计算指标七、结论 一、说明 在时间序列预测领域&#xff0c;对更准确、更高效的模型的追求始终存在。深度学习的应用为该领域的重大进步铺…

深度学习pytorch实战第P2周:CIFAR10彩色图片识别

>- **&#x1f368; 本文为[&#x1f517;365天深度学习训练营](https://mp.weixin.qq.com/s/0dvHCaOoFnW8SCp3JpzKxg) 中的学习记录博客** >- **&#x1f356; 原作者&#xff1a;[K同学啊](https://mtyjkh.blog.csdn.net/)** 零、引言&#xff08;温故而知新&#xff…

C++算法 —— 前缀和

一、【模版】前缀和 1.链接 【模板】前缀和_牛客题霸_牛客网 (nowcoder.com) 2.描述 3.思路 前缀和的思想其实就是一种简单的动态规划&#xff0c;以i位置记录从头位置到i位置的和&#xff0c;然后间接的求一段连续区间的数组和&#xff0c;时间复杂度是O&#xff08;n&…

基于多模态单细胞数据构建共表达网络-MuSeGNN

本篇来自于MuSe-GNN: Learning Unified Gene Representation From Multimodal Biological Graph Data的补充材料。主要目的是从多模态数据中构建共表达网络。作者概述了使用CS-CORE&#xff0c;scTransform和SPARK-X进行预处理步骤和网络构建的算法细节。 目前存在大量用于图谱…

ESP32 引脚分配

请注意&#xff0c;以下引脚分配参考适用于流行的 30 引脚ESP32 devkit v1开发板。 仅输入引脚 GPIO34~39是GPIs–仅输入的管脚。这些引脚没有内部上拉或下拉电阻。它们不能用作输出&#xff0c;因此只能将这些管脚用作输入&#xff1a;GPIO 34、GPIO 35、GPIO 36、GPIO 39 S…

利用nginx-http-flv-module实现三种直播

目录 一、说明 二、目标 三、实现 四、直播地址 一、说明 此文在《流媒体服务器的搭建(支持hls)》《搭建nginx-http-flv-module直播系统》之后编写,很多详细内容需要参考它。 流媒体服务器的搭建(支持hls)

【解读Kubernetes架构】全面指南,带你掌握Kubernetes的设计原理与构成!

了解 Kubernetes 架构&#xff1a;综合指南 前言一、什么是 Kubernetes 架构&#xff1f;1.1、控制平面1.2、工作节点 二、Kubernetes 控制平面组件2.1、kube-api服务器2.2、etcd2.3、kube-scheduler2.4、Kube 控制器管理器2.5、云控制器管理器 &#xff08;CCM&#xff09; 三…

Web APIs简介 Dom

JS的组成 API API 是一些预先定义的函数&#xff0c;目的是提供应用程序与开发人员基于软件或硬件得以访问一组例程的能力&#xff0c;而又无需访问源码&#xff0c;或理解内部工作机制的细节 简单理解&#xff1a;API是给程序员提供的一种工具&#xff0c;以便能更轻松的实现…

车载电子电器架构 —— 工程EOL诊断

车载电子电器架构 —— 工程EOL诊断 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己…

数据的统计描述

data.info() 提供了关于数据框的简要摘要&#xff0c;包括&#xff1a; 索引类型数据列的数量非空值的数量&#xff08;针对每列&#xff09;每列的数据类型&#xff08;例如&#xff0c;int64, float64, object等&#xff09;内存使用情况提供了哪些列可能包含缺失值&#xff…

flink on yarn

前言 Apache Flink&#xff0c;作为大数据处理领域的璀璨明星&#xff0c;以其独特的流处理和批处理一体化模型&#xff0c;成为众多企业和开发者的首选。它不仅能够在处理无界数据流时展现出卓越的实时性能&#xff0c;还能在有界数据批处理上达到高效稳定的效果。本文将简要…

Linux文件IO(4):目录操作和文件属性获取

目录 1. 前言 2. 函数介绍 2.1 访问目录 – opendir 2.2 访问目录 – readdir 2.3 访问目录 – closedir 2.4 修改文件访问权限 – chmod/fchmod 2.5 获取文件属性 – stat/lstat/fstat 2.5.1 文件属性 – struct stat 2.6 文件类型 – st_mode 3. 代码练习 3.1 要求 3.2 代…

day04-MQ

1.初识MQ 1.1.同步和异步通讯 微服务间通讯有同步和异步两种方式&#xff1a; 同步通讯&#xff1a;就像打电话&#xff0c;需要实时响应。异步通讯&#xff1a;就像发邮件&#xff0c;不需要马上回复。 两种方式各有优劣&#xff0c;打电话可以立即得到响应&#xff0c;但是你…

数组--有序数组的平方

LeetCode中的第977题&#xff1a; 思想&#xff1a;①返回每个新数组&#xff1b;②排序&#xff1b; &#xff08;n个数&#xff0c;进行n-1趟比较。第j趟比较中要进行n-j次两两比较&#xff09; &#xff08;1&#xff09;n个数&#xff0c;进行n-1趟比较&#xff1a; for(…

深度学习【向量化(array)】

为什么要向量化 在深度学习安全领域、深度学习练习中&#xff0c;你经常发现在训练大量数据时&#xff0c;深度学习算法表现才更加优越&#xff0c;所以你的代码运行的非常快至关重要&#xff0c;否则&#xff0c;你将要等待非常长的时间去得到结果。所以在深度学习领域向量化…