2594. 修车的最少时间
文章目录
- Tag
- 题目来源
- 题目解读
- 解题思路
- 方法一:二分枚举答案
- 写在最后
Tag
【二分枚举答案】【数组】
题目来源
2594. 修车的最少时间
题目解读
给你一个表示机械工能力的数组 ranks,ranks[i] 表示第 i 位机械工可以在 r a n k s [ i ] ∗ n 2 ranks[i] * n ^2 ranks[i]∗n2 分钟内修好 n 辆车。所有的机械工可以同时修理汽车,返回修理完所有汽车需要的最少时间。
解题思路
方法一:二分枚举答案
如果已知修车的时间为 t t t,那么我们可以计算每个人在 t 分钟内可以修好的车辆数。如果一个工人的修车能力为 r,则有这样的表达式:
r n 2 < = t rn^2 <= t rn2<=t
解得:
n < = t r n <= \sqrt{\frac{t}{r}} n<=rt
于是,能力值为 r 的工人最多可以修车 ⌊ t r ⌋ \lfloor{\frac{t}{r}}\rfloor ⌊rt⌋ 辆。
累加每个机械工在 t 分钟内的修车数量,如果有
∑ i = 0 n − 1 ⌊ t r a n k s [ i ] ⌋ > = c a r s \sum_{i=0}^{n-1}{\lfloor \sqrt{\frac{t}{ranks\left[ i \right]}} \rfloor}>=cars i=0∑n−1⌊ranks[i]t⌋>=cars
则说明可以在 t 分钟内修完所有的车。
上式表明,t 越大,能修好的车子越多。有了这样的单调性,我们就可以二分枚举答案了,二分的上界为修车最快的人修完所有车子的时间即 m i n ( r a n k s ) ⋅ c a r s 2 min(ranks) \cdot cars^2 min(ranks)⋅cars2。
在具体实现中,我们枚举修车的时间 t,如果所有机械工在 t 分钟内修完的汽车数量大于等于 cars,则调整右边界为 t,否则调整左边界为 t+1。
实现代码
class Solution {
public:long long repairCars(vector<int>& ranks, int cars) {int minR = *min_element(ranks.begin(), ranks.end());long long left = 0, right = 1LL * minR * cars * cars;auto check = [&](long long m) {long long cnt = 0;for (int r : ranks) {cnt += sqrt(m / r);}return cnt >= cars;};while (left < right) {long long mid = left + ((right - left) >> 1);if (check(mid)) {right = mid;}else {left = mid + 1;}}return left;}
};
复杂度分析
时间复杂度: O ( n l o g L ) O(nlogL) O(nlogL), n n n 为数组 ranks 的长度, L L L 为二分的上界。
空间复杂度: O ( 1 ) O(1) O(1),因为仅用了常数个变量。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。
相关文章:
2594. 修车的最少时间
文章目录 Tag题目来源题目解读解题思路方法一:二分枚举答案 写在最后 Tag 【二分枚举答案】【数组】 题目来源 2594. 修车的最少时间 题目解读 给你一个表示机械工能力的数组 ranks,ranks[i] 表示第 i 位机械工可以在 r a n k s [ i ] ∗ n 2 ranks[…...
vue 使用qrcode生成二维码并可下载保存
安装qrcode npm install qrcode --save代码 <template><div style"display: flex; flex-direction: column; align-items: center; justify-content center;"><div>查看溯源码,<a id"saveLink" style"text-decorati…...
网络融合的发展思路
虽然移动和固定网的融合代表了下一代网络的发展方向,但是目前移动和固定网的 发展还是独立的,有着各自的演进方式,要实现两个网络的完全融合是一个长期 的、逐步发展的过程。 网络融合的体系结构首先应坚持网络分层和功能分离的原则&#…...
报考浙江工业大学MBA项目如何选择合适的辅导班?
浙江工业大学MBA项目每年有数百人报考,在浙江省内除了浙大以外算是人数比较多的一个项目。2023级的招生中第一志愿也通过复试刷掉了百来人,在省内其实作为第一志愿报考的风险在逐渐增大,考生们如果坚持报考,则在针对联考初试的备考…...
算法训练第五十八天
总结:今日事单调栈的开端,还是挺巧妙的。 496. 下一个更大元素 I - 力扣(LeetCode) 代码: class Solution { public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& …...
如何快速生成一个H5滑动的卡片(单页和分页都有)
单页 <ul class"combo"><li v-for"(item, index) in arr" :key"index"><div class"combo-name">{{ item.A }}</div><div class"combo-price">{{ item.B }}</div><div class"co…...
嵌入式开发笔试面试
C语言部分: 1.gcc的四步编译过程 1.预处理 展开头文件,删除注释、空行等无用内容,替换宏定义。 gcc -E hello.c -o hello.i 2.编译 检查语法错误,如果有错则报错,没有错误则生成汇编文件。 gcc -S hello.i -o h…...
2023国赛数学建模B题思路分析 - 多波束测线问题
# 1 赛题 B 题 多波束测线问题 单波束测深是利用声波在水中的传播特性来测量水体深度的技术。声波在均匀介质中作匀 速直线传播, 在不同界面上产生反射, 利用这一原理,从测量船换能器垂直向海底发射声波信 号,并记录从声波发射到…...
thinkphp6 入门(5)-- 模型是什么 怎么用
一、模型 MVC架构 之前开发一个功能,后端为在控制器(C)中写 php SQL,前端为在页面(V)中写html css js,这就形成了 VC 架构。 但是发现,相同的数据逻辑(SQL…...
Hadoop HDFS 高阶优化方案
目录 一、短路本地读取:Short Circuit Local Reads 1.1 背景 1.2 老版本的设计实现 1.3 安全性改进版设计实现 1.4 短路本地读取配置 1.4.1 libhadoop.so 1.4.2 hdfs-site.xml 1.4.3 查看 Datanode 日志 二、HDFS Block 负载平衡器:Balan…...
通俗易懂讲解大模型:Tokenizer
Tokenizer Tokenizer 是 NLP pipeline 的核心组件之一。Tokenizer 的目标是:将文本转换为模型可以处理的数据。模型只能处理数字,因此 Tokenizer 需要将文本输入转换为数字输入。 通常而言有三种类型的 Tokenizer :Word-based Tokenizer、Cha…...
nested exception is java.io.FileNotFoundException
完整的错误信息: [main] ERROR o.s.boot.SpringApplication - Application run failed org.springframework.beans.factory.BeanDefinitionStoreException: Failed to parse configuration class [com.heima.article.ArticleApplication]; nested exception is java…...
ARM编程模型-常用指令集
一、ARM指令集 ARM是RISC架构,所有的指令长度都是32位,并且大多数指令都在一个单周期内执行。主要特点:指令是条件执行的,内存访问使用Load/store架构。 二、Thumb 指令集 Thumb是一个16位的指令集,是ARM指令集的功能…...
MAC M2芯片执行yolov8 + deepsort 实现目标跟踪
MAC M2芯片执行yolov8 deepsort 实现目标跟踪 MAC M2 YoloX bytetrack实现目标跟踪 实验结果 MAC mps显存太小了跑不动 还是得用服务器跑 需要实验室的服务器跑 因为网上花钱跑4天太贵了!!! 步骤过程尝试: 执行mot17 数据集 …...
使用Python轻松实现文档编写
大家好,本文将介绍如何使用Python轻松实现文档编写,减少报告撰写的痛苦,使用Microsoft Word、python和python-docx库来简化报告撰写和从报告中提取信息。 案例 读取一个Word文档并进行编辑。 虽然听起来可能不那么令人振奋,但根…...
前后端分离项目,整合成jar包,刷新404或空白页,解决方法
问题解决 1、注销遇到404,或刷新遇到404 # 添加错误跳转 Component public class ErrorConfig implements ErrorPageRegistrar {Overridepublic void registerErrorPages(ErrorPageRegistry registry) {ErrorPage error404Page new ErrorPage(HttpStatus.NOT_FOU…...
前端、后端面试集锦
诸位读者,我们在工作的过程中,经常会因跳槽而面试。 你开发能力很强,懂得技术也很多,若加上条理清晰的面试话术,可以让您的面试事半功倍。 个人博客阅读量破170万,为尔倾心打造的 面试专栏-前端、后端面试…...
Web存储
目录 什么是 HTML5 Web 存储? 方法 cookie webStorage 会话存储 sessionStorage 本地存储localStorage 什么是 HTML5 Web 存储? 使用HTML5可以在本地存储用户的浏览数据。 早些时候,本地存储使用的是 cookie。但是Web 存储需要更加的安全与快速. 这些数据不会被保存在服…...
字节对齐(C++,C#)
C#字节对齐示例 结构体定义 [StructLayoutAttribute(LayoutKind.Sequential, CharSet CharSet.Ansi, Pack 1)],这是C#引用非托管的C/C的DLL的一种定义定义结构体的方式,主要是为了内存中排序,LayoutKind有两个属性Sequential和Explicit&a…...
使用mybatisplus查询sql时,报Error attempting to get column ‘ID‘ from result set错误
问题描述: 在使用如下代码进行查询时,报Error attempting to get column ‘ID’ from result set错误: LambdaQueryWrapper<TimeFeature> wrapper new LambdaQueryWrapper<>();wrapper.eq(TimeFeature::getDate, currentDateTim…...
Wan2.1视频生成小白必看:避开这些坑,让你的视频生成一次成功
Wan2.1视频生成小白必看:避开这些坑,让你的视频生成一次成功 1. 为什么你的视频生成总是失败? 很多新手第一次使用Wan2.1视频生成模型时,都会遇到各种问题:生成的视频模糊不清、内容与描述不符、甚至直接失败。这通常…...
STEP3-VL-10B实际作品集:MMBench 92.05分视觉识别能力高清图文输出示例
STEP3-VL-10B实际作品集:MMBench 92.05分视觉识别能力高清图文输出示例 1. 引言:当AI“看懂”了世界 你有没有想过,让AI像人一样“看懂”一张图片,到底有多难? 这不仅仅是识别出图片里有什么东西那么简单。比如给你…...
告别布局跳动!Android Dialog+EditText+软键盘的终极适配指南(含Kotlin代码)
Android Dialog软键盘适配全攻略:从布局跳动到完美交互 在Android开发中,Dialog与软键盘的交互一直是让开发者头疼的问题。当EditText获得焦点时,弹出的软键盘经常会遮挡输入框或导致布局跳动,严重影响用户体验。本文将深入探讨Di…...
Fay数字人框架终极指南:30分钟打造你的AI虚拟助手
Fay数字人框架终极指南:30分钟打造你的AI虚拟助手 【免费下载链接】Fay Fay 是一个开源的数字人类框架,集成了语言模型和数字字符。它为各种应用程序提供零售、助手和代理版本,如虚拟购物指南、广播公司、助理、服务员、教师以及基于语音或文…...
告别UnsatisfiedLinkError!OpenCV Java版环境配置的终极避坑指南(含Maven/Gradle依赖)
告别UnsatisfiedLinkError!OpenCV Java版环境配置的终极避坑指南(含Maven/Gradle依赖) 在计算机视觉领域,OpenCV无疑是开发者最常用的工具库之一。然而,当Java开发者满怀期待地引入OpenCV依赖后,却常常被U…...
Stable Diffusion工作流升级:Pixel Fashion Atelier预设Prompt库详解
Stable Diffusion工作流升级:Pixel Fashion Atelier预设Prompt库详解 1. 项目概述 像素时装锻造坊(Pixel Fashion Atelier)是一款基于Stable Diffusion与Anything-v5模型的图像生成工作站。这个创新工具将复古日系RPG的视觉风格与现代AI图像…...
银发健康消费“新战场”:线下渠道红利期开启,10+嘉宾重磅分享实战方法论
银发经济与连锁药店转型的双向奔赴整理 | AgeClub内容团队前言当前,中国银发经济已成为国内增长最快的赛道之一。数据显示,我国银发经济市场规模已突破 10 万亿元,未来整体规模有望超过 30 万亿元。精准对接优质渠道,成为众多银…...
3分钟上手:ControlNet-v1-1_fp16_safetensors让你的AI绘画更精准可控 [特殊字符]
3分钟上手:ControlNet-v1-1_fp16_safetensors让你的AI绘画更精准可控 🎨 【免费下载链接】ControlNet-v1-1_fp16_safetensors 项目地址: https://ai.gitcode.com/hf_mirrors/comfyanonymous/ControlNet-v1-1_fp16_safetensors ControlNet-v1-1_f…...
Java函数计算部署实战:从本地调试到生产环境上线的7个关键步骤(含阿里云/华为云/AWS对比)
第一章:Java函数计算部署全景概览Java函数计算是云原生场景下轻量级、事件驱动型服务的重要实现方式。它将传统Java应用的部署范式从虚拟机/容器迁移至按需执行、自动扩缩的无服务器架构,显著降低运维复杂度与资源闲置成本。开发者只需聚焦业务逻辑&…...
203 异构车辆队列分布式 MPC 优化控制约束复现之旅
203 异构车辆队列分布式 MPC 优化控制约束 复现的代码 .m 文件在自动驾驶和智能交通领域,异构车辆队列的分布式模型预测控制(MPC)是个热门话题。今天就来聊聊基于复现代码(.m文件)对203异构车辆队列分布式MPC优化控制约…...
