LeetCode LCP 12. 小张刷题计划(二分查找)
发布日期:2021-07-01 03:25:06
浏览次数:2
分类:技术文章
本文共 1808 字,大约阅读时间需要 6 分钟。
1. 题目
为了提高自己的代码能力,小张制定了 LeetCode 刷题计划,他选中了 LeetCode 题库中的 n 道题,编号从 0 到 n-1,并计划在 m 天内按照题目编号顺序刷完所有的题目(注意,小张不能用多天完成同一题)。
在小张刷题计划中,小张需要用 time[i]
的时间完成编号 i 的题目。
我们定义 m 天中做题时间最多的一天耗时为 T(小杨完成的题目不计入做题总时间)。
请你帮小张求出最小的 T是多少。示例 1:输入:time = [1,2,3,3], m = 2输出:3解释:第一天小张完成前三题,其中第三题找小杨帮忙;第二天完成第四题,并且找小杨帮忙。这样做题时间最多的一天花费了 3 的时间,并且这个值是最小的。示例 2:输入:time = [999,999,999], m = 4输出:0解释:在前三天中,小张每天求助小杨一次,这样他可以在三天内完成所有的题目并不花任何时间。限制:1 <= time.length <= 10^51 <= time[i] <= 100001 <= m <= 1000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/xiao-zhang-shua-ti-ji-hua 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
类似题目:
class Solution { public: int minTime(vector & time, int m) { int Tl = 0, Tr = 0, Tmid, i, n = time.size(); for(i = 0; i < n; ++i) Tr += time[i];//最大时间上限 while(Tl <= Tr) { //二分查找 Tmid = Tl+((Tr-Tl)>>1); if(check(time,Tmid,m))//每天最多使用Tmid时间,m天可以完成吗? Tr = Tmid-1; else Tl = Tmid+1; } return Tl; } bool check(vector & time, int t, int m) { //每天最多花费t时间, 小于等于m天做完 int maxCost = 0, days = 1, totalcost = 0, i;//都不用求助的话,最少天数1天 bool chancetohelp = true;//有机会求助 for(i = 0; i < time.size(); ++i) { maxCost = max(maxCost, time[i]);//最耗时的题 totalcost += time[i];//当天花费总时间 if(totalcost > t)//超过限制 { if(chancetohelp)//可以求助 { chancetohelp = false; totalcost -= maxCost;//求助使用,耗时最多的 } else//不能求助了 { days++;//开启新的一天 totalcost = 0;//当天累积清零 maxCost = 0;//最大费时的题目清零 i--;//刚才的题目,还没做,回去做去 chancetohelp = true;//新的一天有一次求助机会 } } } return days <= m;//m天可以完成刷题 }};
172 ms 28.8 MB
转载地址:https://michael.blog.csdn.net/article/details/105921940 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月26日 09时53分31秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
结合一道面试题 看c语言运算符的执行顺序
2019-05-03
Objective-C的内省方法介绍
2019-05-03
Objective-C 内存管理 看这个就够啦
2019-05-03
IOS开发--微信支付
2019-05-03
iOS 微信支付 实用教程
2019-05-03
UIViewController的基本概念与生命周期
2019-05-03
最新方法制作自己的cocoapods开源框架的详细步骤
2019-05-03
Getting start with OCMock in you unit test
2019-05-03
李洪强和你一起学习前端之(1)Html基础
2019-05-03
李洪强iOS经典面试题142-第三方框架及其管理
2019-05-03
李洪强经典面试题38
2019-05-03
我们必须自学
2019-05-03
iOS应用内付费(IAP)开发步骤列表
2019-05-03
iOS-TextField知多少
2019-05-03
用javascript协助导入图片
2019-05-03
白话 Ruby 与 DSL 以及在 iOS 开发中的运用
2019-05-03
获取任意线程调用栈的那些事
2019-05-03
主线程中也不绝对安全的 UI 操作
2019-05-03
深入研究 Runloop 与线程保活
2019-05-03