動機

經典的binary search題

  • 注意結果是不是連續的!!

Problem

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

 

Example 1:

Input: nums = [7,2,5,10,8], m = 2Output: 18Explanation:There are four ways to split nums into two subarrays.The best way is to split it into [7,2,5] and [10,8],where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], m = 2Output: 9

Example 3:

Input: nums = [1,4,4], m = 3Output: 4

 

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 106
  • 1 <= m <= min(50, nums.length)

Sol

去割算總數，bsearch 同時留一個位置存最大的數

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def split(limit):
            cnt = nums[0]
            ret = 0
            big = 0
            for n in nums[1:]:
                if n > limit:
                    return float('inf'), None
                if cnt+n > limit:
                    big = max(big,cnt)
                    cnt = n
                    ret += 1
                else:
                    cnt += n
            big = max(big,cnt)
            return ret+1, big
        if len(nums) == m:
            return max(nums)
        a,b = 0, sum(nums)+1
        big = 0
        while a<b:
            mid = (a+b)//2
            gps,n = split(mid)
            #print(a,mid,b,gps,n)
            if gps <= m:
                big = n
                b = mid
            else:
                a = mid+1
        return big