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

算法练习题24——leetcode3296移山所需的最小秒数(二分模拟)

【题目描述】

 

【代码示例(java)】

class Solution {// 计算让工人们将山的高度降到0所需的最少时间public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {long left = 0; // 最少时间初始为0long right = 0; // 最大时间初始化为0// 计算每个工人在最坏情况下,单独完成整个山的工作所需的最大时间for (int workTime : workerTimes) {// workTime 是工人降低1个单位高度所需的时间// 公式计算从1降低到mountainHeight所需的总时间// 总工作量:1 + 2 + ... + mountainHeight = (mountainHeight * (mountainHeight + 1)) / 2// 总时间就是工人工作时间乘以这个总工作量right = Math.max(right, (long) workTime * (mountainHeight * (mountainHeight + 1L)) / 2L);}// 使用二分查找来寻找完成任务的最少时间// 这里的范围是 [left, right]while (left < right) {long mid = left + (right - left) / 2; // 计算中间时间,防止溢出// 检查在mid秒内是否可以完成任务if (can(mountainHeight, workerTimes, mid)) {right = mid; // 如果可以完成任务,缩小右边界} else {left = mid + 1; // 如果不能完成任务,增加左边界}}return left; // left即为最小的可以完成任务的时间}// 检查工人们能否在给定的time秒内将山的高度降到0private boolean can(int mountainHeight, int[] workerTimes, long time) {long totalReduceHeight = 0; // 总共降低的高度初始化为0// 遍历每个工人,计算他们在time秒内可以降低的最大高度for (int workTime : workerTimes) {long left = 0; // 当前工人能降低的最小高度初始化为0long right = mountainHeight; // 当前工人能降低的最大高度不会超过mountainHeight// 使用二分查找计算该工人在给定time秒内可以降低的最大高度while (left < right) {// 计算mid,这个mid是该工人可能降低的单位高度long mid = left + (right - left + 1) / 2; // 这里加1是为了偏向右边,避免死循环// 计算该工人降低mid个单位高度所需的时间:工作时间 * (1 + 2 + ... + mid)long requiredTime = workTime * mid * (mid + 1) / 2;// 如果当前时间够用,说明可以降低mid个单位高度if (requiredTime <= time) {left = mid; // 时间足够,增加高度} else {right = mid - 1; // 时间不足,降低高度}}// 当前工人能降低的最大高度是lefttotalReduceHeight += left; // 将该工人降低的高度累计到总高度上// 如果总的降低高度已经达到或超过山的高度,则任务可以完成,提前返回trueif (totalReduceHeight >= mountainHeight) {return true;}}// 如果所有工人合计降低的高度不足以将山的高度降为0,返回falsereturn totalReduceHeight >= mountainHeight;}
}

【最大值公式】

就是一个等差数列求和,加 L 是为了确保该数字被视为 long 类型,这样可以避免在大数计算时溢出的问题。在这道题的情况下,mountainHeight 可能会很大,因此在某些运算中需要将其转换为 long 类型来确保计算的正确性。 

好难 我要缺氧了谁来救我 谁 来 救救 本 小 主 哭.....

相关文章:

算法练习题24——leetcode3296移山所需的最小秒数(二分模拟)

【题目描述】 【代码示例&#xff08;java&#xff09;】 class Solution {// 计算让工人们将山的高度降到0所需的最少时间public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {long left 0; // 最少时间初始为0long right 0; // 最大时间初始化为0// …...

excel 单元格一直显示年月日

excel 单元格一直显示年月日&#xff0c;在单元格上右键选择单元格格式&#xff0c;选择日期时单元格会显示成日期格式...

【线程】线程的控制

本文重点&#xff1a;理解线程控制的接口 前言 内核中是没有很明确线程的概念的&#xff0c;只有轻量级进程的概念&#xff0c;不会提供直接给我们线程的系统调用&#xff0c;而会给我们提供轻量级进程的系统调用。我们用户是需要线程的接口的&#xff0c;在应用层&#xff0…...

掌握 Spring:从新手到高手的常见问题汇总

一提起Spring&#xff0c;总感觉有太多知识&#xff0c;无法详尽&#xff0c;有些基础理解就先不说了&#xff0c;相信大家都已经用过Spring了 下面简单针对常见Spring面试题做些回答 核心特性 IOC容器spring事件资源管理国际化校验数据绑定类型转换spirng表达式面向切面编程……...

机器学习——Bagging

Bagging&#xff1a; 方法&#xff1a;集成n个base learner模型&#xff0c;每个模型都对原始数据集进行有放回的随机采样获得随机数据集&#xff0c;然后并行训练。 回归问题&#xff1a;n个base模型进行预测&#xff0c;将得到的预测值取平均得到最终结果。 分类问题&#xf…...

日志体系结构与框架:历史、实现与如何在 Spring Cloud 中使用日志体系

文章目录 1. 引言2. 日志体系结构3. 日志框架的发展历程日志框架特点对比 4. 日志记录器的使用与管理使用 SLF4J 和 Logback 的日志记录示例 5. Spring Cloud 中的日志使用5.1 日志框架集成5.2 分布式追踪&#xff1a;Spring Cloud Sleuth 和 Zipkin添加 Sleuth 和 Zipkin 依赖…...

图文深入理解SQL语句的执行过程

List item 本文将深入介绍SQL语句的执行过程。 一.在RDBMS&#xff08;关系型DB&#xff09;中&#xff0c;看似很简单的一条已写入DB内存的SQL语句执行过程却非常复杂&#xff0c;也就是说&#xff0c;你执行了一条诸如select count(*) where id 001 from table_name的非常简…...

ubuntu安装StarQuant

安装boost 下面展示一些 内联代码片。 sudo apt install libboost-all-dev -y安装libmongoc-1.0 链接: link // An highlighted block sudo apt install libmongoc-1.0-0 sudo apt install libbson-1.0 sudo apt install cmake libssl-dev libsasl2-dev编译源码 $ git clone…...

学习篇 | Jupyter 使用(notebook hub)

1. JupyterHub 1.1 快速尝试 jupyterhub -f/path/jupyter_config.py --no-ssl1.2 长期后台运行 bash -c "nohup jupyterhub -f/path/jupyter_config.py --no-ssl" > ~/jupyterhub.log 2>&1 &1.3 帮助 jupyterhub --help2. Jupyter Notebook 2.1 快…...

【裸机装机系列】8.kali(ubuntu)-虚拟内存swap交换分区扩展

推荐阅读&#xff1a; 1.kali(ubuntu)-为什么弃用ubuntu&#xff0c;而选择基于debian的kali操作系统 linux swap交换分区&#xff0c;相当于win系统虚拟内存的概念。当linux系统的物理内存不够用的时候&#xff0c;就需要将物理内存中的一部分空间释放出来&#xff0c;以供当前…...

异步请求的方法以及原理

异步请求是指在发送请求后&#xff0c;不会阻塞程序的执行&#xff0c;而是继续执行后续的代码&#xff0c;等待请求返回后再执行相应的回调函数。常见的异步请求方法包括使用XMLHttpRequest对象&#xff08;XHR&#xff09;和fetch API。 异步请求的方法 1. XMLHttpRequest (X…...

SpringCloud入门(六)Nacos注册中心(下)

一、Nacos环境隔离 Nacos提供了namespace来实现环境隔离功能。 nacos中可以有多个namespace。namespace下可以有group、service等。不同namespace之间相互隔离&#xff0c;例如不同namespace的服务互相不可见。 使用Nacos Namespace 环境隔离 步骤&#xff1a; 1.在Nacos控制…...

【RDMA】mlxlink检查和调试连接状态及相关问题--驱动工具

简介 mlxlink工具用于检查和调试连接状态及相关问题。该工具可以用于不同的链路和电缆&#xff08;包括被动、电动、收发器和背板&#xff09;。 属于mft工具套件的一个工具&#xff0c;固件工具 Firmware Tools (MFT):https://blog.csdn.net/bandaoyu/article/details/14242…...

QT For Android开发-打开PPT文件

一、前言 需求&#xff1a; Qt开发Android程序过程中&#xff0c;点击按钮就打开一个PPT文件。 Qt在Windows上要打开PPT文件或者其他文件很容易。可以使用QDesktopServices打开文件&#xff0c;非常方便。QDesktopServices提供了静态接口调用系统级别的功能。 这里用的QDesk…...

SpringBoot教程(三十) | SpringBoot集成Shiro权限框架

SpringBoot教程&#xff08;三十&#xff09; | SpringBoot集成Shiro权限框架 一、 什么是Shiro二、Shiro 组件核心组件其他组件 三、流程说明shiro的运行流程 四、SpringBoot 集成 Shiro &#xff08;shiro-spring-boot-web-starter方式&#xff09;1. 添加 Shiro 相关 maven2…...

[ffmpeg] 视频格式转换

本文主要梳理 ffmpeg 中的视频格式转换。由于上屏的数据是 rgba&#xff0c;编码使用的是 yuv数据&#xff0c;所以经常会使用到视频格式的转换。 除了使用 ffmpeg进行转换&#xff0c;还可以通过 libyuv 和 directX 写 shader 进行转换。 之前看到文章说 libyuv 之前是 ffmpeg…...

git-repo系列教程(3) git-repo https证书认证问题

文章目录 问题描述解决步骤1.下载证书2.测试证书是否正常3.设置环境变量 总结 问题描述 在使用git repo 同步仓库时,发现不能同步,出现如下提示错误: % Total % Received % Xferd Average Speed Time Time Time CurrentDload Upload Total Spent Left …...

中序遍历二叉树全过程图解

文章目录 中序遍历图解总结拓展&#xff1a;回归与回溯 中序遍历图解 首先看下中序遍历的代码&#xff0c;其接受一个根结点root作为参数&#xff0c;判断根节点是否为nil&#xff0c;不为nil则先递归遍历左子树。 func traversal(root *TreeNode,res *[]int) {if root nil …...

设计模式 组合模式(Composite Pattern)

组合模式简绍 组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许你将对象组合成树形结构来表示“部分-整体”的层次结构。组合模式使得客户端可以用一致的方式处理单个对象和组合对象。这样&#xff0c;可以在不知道对象具体类型的条…...

在vue中嵌入vitepress,基于markdown文件生成静态网页从而嵌入社团周报系统的一些想法和思路

什么是vitepress vitepress是一种将markdown文件渲染成静态网页的技术 其使用仅需几行命令即可 //在根目录安装vitepress npm add -D vitepress //初始化vitepress&#xff0c;添加相关配置文件&#xff0c;选择主题&#xff0c;描述&#xff0c;框架等 npx vitepress init //…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...