Description
You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.
You want to share the chocolate with your k friends so you start cutting the chocolate bar into k + 1 pieces using k cuts, each piece consists of some consecutive chunks.
Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.
Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.
Example
Example 1:
Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6
Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]
Example 2:
Input: sweetness = [5,6,7,8,9,1,2,3,4], k = 8
Output: 1
Explanation: There is only one way to cut the bar into 9 pieces.
Example 3:
Input: sweetness = [1,2,2,1,2,2,1,2,2], k = 2
Output: 5
Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]
Approach
From the problem description, we want to make sure that we are searching for the maximum. Make sure this is made clear first, where binary search problems often contain both the words minimum and maximum at the same time.
Then, we can structure the binary search in the form whenever we find an available answer, we would update the variable ans and test larger values.
For the testing part, once we have selected a minimal sweetness x to test, we just need to traverse the chocolate bar chunk by chunk and sum the sweetness. Once the total sweetness of a piece reaches x, then we cut the current piece off of the bar and start building the next piece. Since we want to see if the cutting plan works in the best case, there is no need to add any more chunks to a piece once it reaches the minimum sweetness x.
Solution
def canDivide(sweetness, val, k):
chunkCnt = 0
curSweet = 0
pieceCnt = 0
while chunkCnt < len(sweetness):
#print(k, val, curSweet, pieceCnt)
curSweet += sweetness[chunkCnt]
if curSweet >= val:
pieceCnt += 1
curSweet = 0
chunkCnt += 1
if pieceCnt >= k + 1: return True
return False
class Solution(object):
def maximizeSweetness(self, sweetness, k):
left = 0
right = 1e9
ans = -1
while left <= right:
mid = int(left + (right - left) / 2)
cutAvailable = canDivide(sweetness, mid, k)
if cutAvailable:
left = mid + 1
ans = mid
else:
right = mid - 1
return ans
