【416】【移山所需的最少秒数】

devtools/2024/9/22 15:46:02/

又是一周力扣赛

我这里犯了个错误,我开始认为sort一下,然后对最快的工人进行"压榨",完成mount高的山就是最少秒数。

python">class Solution:def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:workerTimes.sort() return workerTimes[0]*mountainHeight*(mountainHeight+1)/2

包错误的。

正确思路应该是使用二分查找,查找对象为时间,然后再根据设定的时间来查看是否完成工作。

python">class Solution:def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:def finish(timelimit):#检查工作是否完成#注意是工人同时工作total=0for time in workerTimes:x = 0while (time * (x + 1)) <= timelimit:x += 1total+=xreturn total>=mountainHeightleft,right=0,max(workerTimes)*mountainHeightwhile left<right:mid=(left+right)//2if finish(mid):#继续查找更小right=midelse:left=mid+1return left

不能这样算,唉,ai也挺逆天的。

这样基于时间求高度是本末倒置,浪费时间复杂度的。

不对,貌似计算公式错误了。

原来是求根公式

python">class Solution:def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:def finish(timelimit):#检查工作是否完成#注意是工人同时工作total = 0for wt in workerTimes:delta = 1 + 8 * timelimit / wtif delta < 0:continuex = int((math.isqrt(int(delta)) -1) //2)total += xif total >= mountainHeight:return Truereturn total>=mountainHeightleft,right=0,max(workerTimes)*mountainHeight*(mountainHeight+1)//2while left<right:mid=(left+right)//2if finish(mid):#继续查找更小right=midelse:left=mid+1return left


http://www.ppmy.cn/devtools/115530.html

相关文章

手写Spring

简单实现Spring基于注解配置 ComponentScan Target(ElementType.TYPE) Retention(RetentionPolicy.RUNTIME) public interface ComponentScan {String value() default ""; } 相当于component-scan HspSpringConfig ComponentScan(value "spring.write.com…

面试金典题9

字符串轮转。给定两个字符串s1和s2&#xff0c;请编写代码检查s2是否为s1旋转而成&#xff08;比如&#xff0c;waterbottle是erbottlewat旋转后的字符串&#xff09;。 示例1: 输入&#xff1a;s1 "waterbottle", s2 "erbottlewat"输出&#xff1a;Tru…

计算机毕业设计Python知识图谱美团美食推荐系统 美团餐厅推荐系统 美团推荐系统 美食价格预测 美团爬虫 美食数据分析 美食可视化大屏

《Python知识图谱美团美食推荐系统》开题报告 一、研究背景与意义 随着信息技术的飞速发展和互联网应用的普及&#xff0c;人们的消费习惯逐渐从线下转移到线上&#xff0c;外卖行业迎来了前所未有的发展机遇。美团作为国内领先的生活服务电子商务平台&#xff0c;拥有庞大的…

【kafka-03】springboot整合kafka以及核心参数详解

Kafka系列整体栏目 内容链接地址【一】afka安装和基本核心概念https://zhenghuisheng.blog.csdn.net/article/details/142213307【二】kafka集群搭建https://zhenghuisheng.blog.csdn.net/article/details/142253288【三】springboot整合kafka以及核心参数详解https://zhenghui…

MySQL版本问题无法使用 group by xxx

mysql命令gruop by报错this is incompatible with sql_modeonly_full_group_by 在mysql 工具 搜索或者插入数据时报下面错误&#xff1a; ERROR 1055 (42000): Expression #1 of SELECT list is not in GROUP BY clause and contains nonaggregated column database_tl.emp.i…

CSS从入门到精通(已完结)

关注作者微信公众号&#xff0c;开启探索更多 CSS 知识的精彩之旅。在这里&#xff0c;你将收获丰富的 CSS 专业内容&#xff0c;深入了解这一网页开发语言的奥秘&#xff0c;不断拓展你的知识边界&#xff0c;提升技能水平。快来关注吧&#xff01; 微信公众号专栏地址&#x…

C++两点成一线

目录 开头程序程序的流程图程序执行的效果下一篇博客要说的东西 开头 大家好&#xff0c;我叫这是我58。 程序 #include <iostream> #include <cstring> #include <Windows.h> #define PANADD(A,B) ((A) < (B) ? 1 : -1) using namespace std; void p…

IS-ISv4/6双栈

文章目录 IS-ISv4/6双栈实验要求配置 IS-ISv4/6双栈 实验要求 配置双栈 R1、2、3、4配置 IS-ISv4 和 IS-ISv6&#xff0c;配置IPv6多拓扑 上面为Level-1类型、中间为Level-1-2、下面是Level-2类型 还有就是说ATT位置1有一定要求连接L1/2连接L1或者L2类型路由器&#xff0c;至…