当前位置: 首页 > 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 //…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...