↓Skip to main content
  1. Posts/

LeetCode-LCP12 小张刷题计划

·1 min·
Table of Contents

LeetCode-LCP12 小张刷题计划 #

Solution 1 #

费用最小化 + 线性判断，二分搜索。

代码如下:

class Solution:
    def minTime(self, time: List[int], m: int) -> int:
        n = len(time)

        def check(t: int) -> bool:
            cnt = 1
            sum_val = 0
            max_val = -1
            for i in range(n):
                sum_val += time[i]
                if time[i] > max_val:
                    max_val = time[i]
                if sum_val - max_val > t:
                    cnt += 1
                    sum_val = max_val = time[i]
                if cnt > m:
                    return False
            return True
        
        l, r = 0, max(time) * (n // m + 1)
        while l <= r:
            mid = (l + r) // 2
            if check(mid):
                r = mid - 1
            else:
                l = mid + 1
        return r + 1