来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/divide-chocolate

1231. 分享巧克力
      你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。

你打算和 K 名朋友一起分享这块巧克力，所以你需要将切割 K 次才能得到 K+1 块，每一块都由一些 连续 的小块组成。

为了表现出你的慷慨，你将会吃掉 总甜度最小 的一块，并将其余几块分给你的朋友们。

请找出一个最佳的切割策略，使得你所分得的巧克力 总甜度最大，并返回这个 最大总甜度。

示例 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

思路：

1. 首先注意这块蛋糕是连续的，切割后的小块蛋糕也必须是连续的；
2. 二分查找 切割的块的大小sweetsize
   如果以当前sweetsize进行切割，切割块数 >= K+1，则sweetsize偏小,left = mid + 1，并更新out；
   如果以当前sweetsize进行切割，切割块数 < K+1，则sweetsize偏大，right = mid - 1，并更新out；

class Solution {
public:
	int GetBlockNum(vector<int>& sweetness, int target)
	{
		int cnt = 0;
		int tmpSum = 0;
		for (auto& i : sweetness) {
			tmpSum += i;
			if (tmpSum >= target) {
				cnt++;
				tmpSum = 0;
			}
		}
		return cnt;
	}

	int maximizeSweetness(vector<int>& sweetness, int K) {
		if (sweetness.size() == 0) {
			return 0;
		}
		int minVal = 0x7FFFFFFF; // init with the biggest value 0x7FFFFFFF for minVal.
		int sum = 0;
		for (auto& i : sweetness) {
			minVal = min(i, minVal);
			sum += i;
		}
		if (K == 0) {
			return sum;
		}
		if (K + 1 >= sweetness.size()) {
			return minVal;
		}
		int out = minVal;
		int begin = minVal;
		int end = sum;
		while (1) {
			if (begin > end) { // key1，不是begin >= end，否则会少遍历begin==end的情况；
				break;
			}
			int mid = (begin + end) / 2;
			int blockNum = GetBlockNum(sweetness, mid);
			if (blockNum >= K + 1) {
				begin = mid + 1; // key2, 需要+1
				out = max(mid, out);
				continue;
			} else { // blockNum < K + 1
				end = mid - 1; // key3, 需要-1
				continue;
			}
		}
		return out;
	}
};