1231 - Divide Chocolate
Written on February 3, 2020
Tweet
class Solution:
def maximizeSweetness(self, sweetness: List[int], K: int) -> int:
lo, hi = min(sweetness), sum(sweetness)
while lo <= hi:
mid = (lo + hi) // 2
if self.is_valid(sweetness, K, mid):
hi = mid - 1
#1) divide the array into m parts and each part is larger than mid
#2) fail to divide into m parts
else:
lo = mid + 1
return lo
def is_valid(self, sweetness, K, target):
curr, count = 0, 1
for s in sweetness:
curr += s
if curr > target:
curr = 0
count += 1
if count > K + 1:
return False
return True