LeetCode 1231. 分享巧克力（极小极大化 二分查找）

示例 1：
输入：sweetness = [1,2,3,4,5,6,7,8,9], K = 5
输出：6
解释：你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。

示例 2：
输入：sweetness = [5,6,7,8,9,1,2,3,4], K = 8
输出：1
解释：只有一种办法可以把巧克力分成 9 块。

示例 3：
输入：sweetness = [1,2,2,1,2,2,1,2,2], K = 2
输出：5
解释：你可以把巧克力分成 [1,2,2], [1,2,2], [1,2,2]。
 
提示：
0 <= K < sweetness.length <= 10^4
1 <= sweetness[i] <= 10^5

class Solution {
public:
    int maximizeSweetness(vector<int>& sweetness, int K) {
    	int l = 0, r = 1e9, mid, ans=0;
        K++;//包含自己
    	while(l <= r)
    	{
    		mid = l+((r-l)>>1);
    		if(!cansplitK(sweetness, mid,K))
    			r = mid-1;
    		else
    			ans = mid, l = mid+1;
    	}
    	return ans;
    }
    bool cansplitK(vector<int>& sweet, int s, int K)
    {
    	int people = 0, total = 0;
    	for(int i = 0; i < sweet.size(); ++i)
    	{
    		total += sweet[i];
    		if(total >= s)
    		{
    			people++;
    			total = 0;
    			if(people >= K)
    				return true;
    		}
    	}
    	return people >= K;
    }
};