蓝桥杯 Java 青蛙过河

 

 

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

/**
  二分法从大(n)到小找足够小的步长
  前缀和记录每个位置的前面有的总石头数(一个石头表示可以容纳一个青蛙,一位置有多少个石头hi就是多少),方便计算
  相当于2x个青蛙从起点到终点
  起点0个石头,终点无数个石头,代表可以容纳无数个青蛙
  检查步长是否符合要求:
    对每个点检查
    如果这个点能跳到的区域内的石头数够2x(也就是下一步可以容纳2x个青蛙)(这一步用两个前缀和相减获得)
    如果当前点的可跳区域包含终点就相当于可以直接到终点,而前面肯定是算了可以到当前点的

  举例:
  按题目意思h就为
  0 1 0 1 0 INF
  前缀和就为
  0 1 1 2 2 INF

  如果步长为2
  那么先检查索引为0的点
  0 1 2 3 4 5
  可跳点为 1 2
  该区域总石头数为 1 - 0 = 1 < 2x
  也就是说青蛙如果在索引为0的点以当前步长能力无法跳到下一区域

  如果步长为4
  那么先检查索引为0的点
  0 1 2 3 4 5
  可跳点为 1 2 3 4
  该区域总石头数为 2 - 0 = 2 = 2x
  也就是说青蛙如果在索引为0的点以当前步长能力能跳到下一区域
  检查索引为1,该点可以直接跳到终点
  所以步长为4可以

  优化:
    前缀和不用考虑终点,终点直接利用长度判定即可
*/
public class Main {
    static int n,x;
    static int[] q;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        x = scan.nextInt();
        q = new int[n];
        for(int i = 1;i < n;i++)
            q[i] = scan.nextInt() + q[i-1];
        
        int l=0;
        int r=n;
        // 二分法提高寻找最小区间(步长k=l)的效率
        while(l < r) {
            //如果该步长符合要求——该步长内的所有连续区间承受的跳跃次数>2*x
            //则缩小k
            int mid = (l + r)/2;
            if(check(mid))
                r = mid;
            //反之,扩大k
            else
                l = mid + 1;
        }
        //直到找到理论上最小就可以满足的步长K(==l)
        System.out.print(l);
        scan.close();
    }
    private static boolean check(int k) {
        //遍历所有步长为k的连续区间
        for(int i=0;i<n-k;i++)
            if(q[i+k]-q[i]<2*x)
                return false;
        return true;
    }
}

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

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

相关文章

【动态基础】从暴力递归到动态规划

C面经汇总 系列综述&#xff1a; 目的&#xff1a;本系列是个人整理为了秋招和实习面试的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡背诵量与深入程度。 来源&#xff1a;材料主要源于算法大神&#xff08;左程云&#xff09;教你从暴力递归到动态规划进行的&#xf…

文件上传预览下载

文件上传的表单必须满足三个条件: 1.表单组件标签只能用:<input type"file" value"xxx">会自动弹框让用户选择文件 2.请求方式只能用post 3.表单编码格式只能用:mutipart/form-data 根据HTTP协议规定,浏览器每次向后台提交参数,都会对参数进行统一…

【软件安装环境配置】vscode 安装界面没有出现安装路径的选择 的解决,以及vscode的删除的问题

由于vscode 没有删除干净&#xff0c;就会出现vscode 安装的时候&#xff0c;没有出现安装路径的界面&#xff0c;所以可以来到vscode的安装路径&#xff0c;点击 unins000.exe 文件就可以 实现将vscode 相关的文件删除&#xff0c; 如果是删除了整个vscode 安装下的文件&…

GPT做SQL查询引擎的自然语言

目录 面向企业查询的生成式人工智能 步骤1&#xff1a;将示例数据转换为单字符字符串 步骤2&#xff1a;为大型语言模型&#xff08;LM&#xff09;创建提示符 步骤3&#xff1a;将数据发送到OpenAI的API 步骤4&#xff1a;执行GPT返回的SQL代码的结果 步骤5(可选)&#…

Webpack简介及打包演示

Webpack 是一个静态模块打包工具&#xff0c;从入口构建依赖图&#xff0c;打包有关的模块&#xff0c;最后用于展示你的内容 静态模块&#xff1a;编写代码过程中的&#xff0c;html&#xff0c;css&#xff0c; js&#xff0c;图片等固定内容的文件 打包过程&#xff0c;注…

智慧巡查平台(Ionic/Vite/Vue3 移动端) 问题记录

目录 1.环境搭建 1.1 安装 node 16 版本 1.2 安装 ionic7 1.3 创建 vue 项目 2.index.html 3.main.ts 3.1 如何默认使用 ios 样式&#xff1f; 3.2 如何使用 ElmentPlus 国际化&#xff1f; 4.router/xxx 5.打包二三事 5.1 添加打包相关文件 5.1.1 .env.developmen…

linux下安装 Chrome 和 chromedriver 以及 selenium webdriver 使用

1 安装 Chrome yum install https://dl.google.com/linux/direct/google-chrome-stable_current_x86_64.rpm2 下载 chromedriver # 进入下载目录 cd soft/crawler_tools# 查看chrome 版本号 google-chrome --version# 在chromedriver下载地址中找到对应版本&#xff0c;下载对…

yarn install 这个命令安装如何加速

yarn install 命令用来安装项目依赖&#xff0c;其速度受多种因素影响&#xff0c;如网络速度、npm/yarn包的源服务器、以及本地缓存等。以下是一些可能帮助你加速 yarn install 的方法&#xff1a; 1. 使用国内镜像 如果你在中国&#xff0c;可以使用淘宝的 npm 镜像&#x…

Android 类似淘宝的吸顶特效 NestedScrollView+RecycleView

运行图 布局的设计 要实现上面的效果需要搞定NestedScrollView和RecycleView的滑动冲突。有人要问RecycleView为何要滑动自动撑大不就好了么&#xff1f;这个问题其实对于有限的资源加载来说是很好的解决方案&#xff0c;但是如果涉及到的是图文结合的并且有大批量的数据的时候…

Mac用NTFS文件夹读写NTFS硬盘 NTFS能复制多大的文件

Mac作为一款备受欢迎的计算机操作系统&#xff0c;具备了许多令人惊叹的功能和特性。然而&#xff0c;对于一些Mac用户来说&#xff0c;使用NTFS格式的硬盘可能存在一些疑问。他们可能想知道Mac是否能够读写NTFS格式的硬盘&#xff0c;以及NTFS格式的硬盘是否有文件大小的限制。…

.\missyou-0.0.1-SNAPSHOT.jar中没有主清单属性

引用&#xff1a;https://blog.csdn.net/marypiglwy/article/details/132016171 配置的时候 <skip>true</skip> skip设置为true&#xff0c;跳过了执行插件&#xff0c;&#xff0c; <plugin><groupId>org.springframework.boot</groupId><a…

如何使用手机蓝牙设备作为电脑的解锁工具像动态锁那样,蓝牙接近了电脑,电脑自动解锁无需输入开机密码

环境&#xff1a; Win10 专业版 远程解锁 蓝牙解锁小程序 问题描述&#xff1a; 如何使用手机蓝牙设备作为电脑的解锁工具像动态锁那样&#xff0c;蓝牙接近了电脑&#xff0c;电脑自动解锁无需输入开机密码 手机不需要拿出来&#xff0c;在口袋里就可以自动解锁&#xff…

vscode json文件添加注释报错

在vscode中创建json文件&#xff0c;想要注释一波时&#xff0c;发现报了个错&#xff1a;Comments are not permitted in JSON. (521)&#xff0c;意思是JSON中不允许注释 以下为解决方法&#xff1a; 在vscode的右下角中找到这个&#xff0c;点击 在出现的弹窗中输入json wit…

【Mybatis源码】XMLConfigBuilder构建器 - 读取XML配置初始化Configuration对象

XMLConfigBuilder是Mybatis中定义的进行构建Configuration对象的类,此类用于读取XML配置文件创建并初始化Configuration对象; 上一篇中我们介绍了XMLConfigBuilder构建器加载XML配置文件以及创建Configuration对象https://blog.csdn.net/m1729339749/article/details/133983…

Linux shell编程学习笔记16:bash中的关联数组

上一节我们探讨了普通的数组&#xff0c;即使用数字下标来索引数组中不同的元素的数组&#xff0c;也可以称之为索引数组。 相比纯粹的数字&#xff0c;字符串不仅能表明含义&#xff0c;也更便于记忆使用&#xff0c;于是就有了关联数组。 一、关联数组概述 bash 从4.0开始支…

【Linux】部署单机OA项目及搭建spa前后端分离项目

目录 部署OA项目 ​编辑 搭建spa前后端分离项目 后端 前端 配置坏境变量 部署OA项目 在虚拟机中&#xff0c;将项目打包成war文件放置到tomcat根目录下的webapps文件目录下 再在主机数据库中连接数据库&#xff0c;并定义数据库名导入相关的表 继续进入tomcat目录下双击点…

香港服务器运行不正常原因简析

​  网站在线业务的部署需要服务器的存在。于我们而言&#xff0c;租用正规服务商(正规机房)的服务器&#xff0c;一般情况下是会很少出现问题。但&#xff0c;要知道&#xff0c;再稳定的服务器也有出现问题的时候&#xff0c;香港服务器也不例外&#xff0c;而且恰恰这个原…

Windows-Oracle19c 安装详解-含Navicate远程连接配置 - 同时连接Oracle11g和Oracle19c

文章目录 0 说明1 下载链接2 安装&#xff1a;一定要以管理员身份运行&#xff0c;不然后面有可能会报错。3 启动监听4. 登录Oracle4 Navicate远程连接-配置监听4.1 修改监听文件4.2 网络配置助手-配置本地监听端口4.3 Navicate连接成功 5 Navicate同时连接两个Oracle数据库 0 …

SpringBoot 自动配置@EnableAutoConfiguration

自动配置vs自动装配 Spring有两个名字听起来相似的概念&#xff1a;一个是自动装配&#xff0c;一个是自动配置。他们两个只是听起来相似&#xff0c;实际根本不同。自动装配是autowire&#xff0c;自动配置是autoconfiguration&#xff0c;他们之间没有任何关系&#xff0c;概…

科聪协作(复合)移动机器人整体解决方案

协作&#xff08;复合&#xff09;移动机器人&#xff08;AGV/AMR&#xff09;相较传统工业机器人具有更加安全和简单的工作优势&#xff0c;具备较强的发展潜力。协作&#xff08;复合&#xff09;移动机器人安全性和操作的简洁性、灵活性不断提高,优势得到了充分发挥,在越来越…