
LCP 12 小张刷题计划(二分查找)
发布日期:2021-05-07 21:55:22
浏览次数:20
分类:精选文章
本文共 1622 字,大约阅读时间需要 5 分钟。
为了解决这个问题,我们需要找到最小的 T,使得小张在 m 天内完成所有题目,并且每天的做题时间不超过 T。为了优化做题时间,小张可以每天最多一次使用求助功能,减少某道题的做题时间。
方法思路
我们可以使用二分查找来确定最小的 T。具体步骤如下:
问题分析:我们需要在 m 天内完成所有题目,每天的做题时间最多为 T。使用求助功能可以减少某道题的做题时间,但每天只能使用一次求助。
二分查找:我们将 T 的范围设定在 0 到所有题目时间的总和之间。通过二分查找,我们可以快速确定是否存在一个 T,使得在 m 天内完成所有题目。
检查函数:对于给定的 T,模拟是否可以在 m 天内完成所有题目。遍历每道题,累加做题时间。遇到超出 T 的情况时,使用求助功能减少最大做题时间,或者开启新的一天重新开始。
解决代码
from typing import Listclass Solution: def check(self, time: List[int], m: int, mid: int) -> bool: days = 1 current_sum = 0 current_max = 0 can_help = True i = 0 while i < len(time): current_sum += time[i] current_max = max(current_max, time[i]) if current_sum > mid: if can_help: current_sum -= current_max can_help = False else: days += 1 current_sum = 0 current_max = 0 can_help = True i = i # 保持i的位置,重新处理当前i i += 1 return days <= m def minTime(self, time: List[int], m: int) -> int: left = 0 right = sum(time) res = right # 初始化为最大可能值 while left <= right: mid = (left + right) // 2 if self.check(time, m, mid): res = mid right = mid - 1 else: left = mid + 1 return res
代码解释
check 函数:该函数用于检查给定的 T 是否可以在 m 天内完成所有题目。遍历每道题,累加做题时间。当累加的时间超过 T 时,使用求助功能减少最大做题时间,或者开启新的一天重新开始。
minTime 函数:通过二分查找确定最小的 T。初始化二分查找的范围为 0 到所有题目时间的总和。对于每个中间值 T,调用 check 函数检查是否可行,并调整查找范围。
该方法通过二分查找和模拟过程,确保在合理的时间复杂度内找到最优解。
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2025年03月20日 03时30分46秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
ajax 处理请求回来的数据
2019-03-06
vue 不常见操作
2019-03-06
jQuery的事件绑定与触发 - 学习笔记
2019-03-06
解决页面加载闪白问题-背景图片加载优化
2019-03-06
Python处理接口测试的签名
2019-03-06
测试流程规范--测试报告模板
2019-03-06
测试流程规范--提测规范(钉钉、邮件)
2019-03-06
Linux上TCP的几个内核参数调优
2019-03-06
解Bug之路-dubbo流量上线时的非平滑问题
2019-03-06
记一次讲故事机器人的开发-我有故事,让机器人来读
2019-03-06
从Linux源码看Socket(TCP)的listen及连接队列
2019-03-06
高德网络定位算法的演进
2019-03-06
高德算法工程一体化实践和思考
2019-03-06
为亿级用户的美好出行而战!高德地图首届算法大赛落幕 95后北邮在读博士带队夺冠
2019-03-06
重温网络编程——常识(三)
2019-03-06
判断一个数是否是2的幂
2019-03-06
js 闭包(新)
2019-03-06
vscode 编辑python 如何格式化
2019-03-06
正则表达针对html(九)
2019-03-06
seo 回忆录百度基本概念(一)
2019-03-06