class Solution:
def maximizeSweetness(self, A: List[int], K: int) -> int:
"""
x : min sweeetness I will get range [min(A), sum(A)] X range is [min(A),avg(A)]
assuming x = l + (r-l+1)//2, count shares >= K,
if cnt < K: r = mid -1
else: l = mid
"""
"""tc O(Nlg(agv(A))) sc O(1)
constrains: (1)divide A into K+1 <consecutive> chunks => no sort & single chunck not splitable
(2) maximun total sweetness from minimal subarray sum => distribute even as much as possible
===> find a threshold to make (1) each piece <= threshold (2) cnt of seperation == K + 1
1. get max single element, array sum and avg => set left = max(avg,max(A)) ,right sum
2. caculate mid, count seperation
3. adjust threshold, if cnt < K+1, threshold is too big
Note when caculating mid, we need to round up since mid is minimun sweetness each subarray need to achieve
there are 2 small optimization
"""
minA,sumA = A[0],0
for a in A:
minA = min(minA,a)
sumA += a
# edge case: len(A) == K +1, no need to cut, each A[i] for each kid, me get minA , optimization (1)
if len(A) == K + 1:
return minA
avgA = (sumA+K+1-1)//(K+1) # ceil up
l,r = minA, avgA #1,1<<30 also works
while l < r:
mid = l +(r-l+1)//2 # not using l + (r-l)//2 since it will ignor remainers, otherwise TLE
cnt = cur = 0
for a in A:
cur += a
if cur >= mid:
cnt += 1
cur = 0
# optimization (2)
if cnt > K:
break
if cnt < K+1:
r = mid -1
else:
l = mid
return l