使用kotlin完成这个题目:LCP 12. 小张刷题计划 中等 103 相关企业 为了提高自己的代码能力,小张制定了 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^5 1 <= time[i] <= 10000 1 <= m <= 1000
时间: 2024-02-21 15:02:17 浏览: 89
这道题目可以使用二分查找加贪心的思想来解决。我们可以二分出一个做题时间的上限,然后尝试用贪心的思想在 m 天内完成所有题目,使得每天的总时间都不超过这个上限,然后判断能否完成所有题目。如果能完成,说明这个上限太高了,我们需要往更小的时间上限二分;如果不能完成,说明这个上限太低了,需要往更大的时间上限二分。最终找到最小的能完成所有题目的时间上限即可。
下面是 Kotlin 的代码实现:
```kotlin
fun minTime(time: IntArray, m: Int): Int {
var left = 0
var right = time.sum()
while (left < right) {
val mid = (left + right) / 2
if (check(time, m, mid)) {
right = mid
} else {
left = mid + 1
}
}
return left
}
private fun check(time: IntArray, m: Int, limit: Int): Boolean {
var cnt = 1
var curTime = 0
for (t in time) {
if (t > limit) {
return false
}
if (curTime + t > limit) {
cnt++
curTime = t
} else {
curTime += t
}
}
return cnt <= m
}
```
时间复杂度为 $O(n\log_2T)$,其中 $T$ 是所有题目的总时间。
阅读全文
相关推荐
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)