# 1231. Divide Chocolate
###### tags: `Leetcode` `Hard` `Binary Search`
Link: https://leetcode.com/problems/divide-chocolate/
## 思路
和[1011. Capacity To Ship Packages Within D Days](https://hackmd.io/w9w2BtjpSsiVqhx9rhPGkQ)很像
binary search sweetness 找到每个minimum sweetness对应的trunk数
由于需要找到最大的minimum sweetness 所以需要写成```chunks>=k+1```，而不是```chunks>k+1```
所以binary search的需要从最小的sweetness到sum+1（而不是sum）
## Code

class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        int sum = 0, min = 0;
        for(int sweet:sweetness){
            sum += sweet;
            min = Math.min(min, sweet);
        }
        int start = min, end = sum+1;
        while(start<end){
            int mid = start+(end-start)/2;
            int chunks = computeChunks(sweetness, mid);
            if(chunks>=k+1){
                start = mid+1;
            }
            else end = mid;
        }
        if(computeChunks(sweetness, start-1)>=k+1) return start-1;
        return start;
    }
    private int computeChunks(int[] sweetness, int minSweet){
        int chunks = 0;
        int currSweet = 0;
        for(int sweet:sweetness){
            currSweet += sweet;
            if(currSweet>=minSweet){
                chunks += 1;
                currSweet = 0;
            }
        }
        return chunks;
    }
}