题目：分享巧克力

• 你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组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

来源：力扣（LeetCode）第5111题(临时)

链接：https://leetcode-cn.com/problems/divide-chocolate

分析：

• 二分查找 + 贪心算法
• 如果最大甜度是mid，那么小于mid的甜度都能分到，大于mid的甜度都分不到。
• 这就像一个排好序的数组，我们要做的就是不断逼近可以分到的最大值。

代码：

class Solution {
    public int maximizeSweetness(int[] sweetness, int K) {
        int len = sweetness.length;++K; // 切割K次得到K+1块巧克力
        int ans = 0;
        int left = 0, right = (int)1e9 + 50; // 最大情况，全部是10^5，总共有10^4个。
        while (left <= right) { // 二分查找符合的情况
            int mid = right + (left - right >> 1); // mid是你自己分到的最小的那个甜度
            if (check(mid, K, sweetness)) { // 如果自己拿到mid，那么检查能不能至少分到K+1份并且mid是最小的。
                left = mid + 1; // 如果能，那么可能还可以分到更大的甜度。
                ans = Math.max(ans, mid); // 先将符合条件的情况保存下来。
            } else {
                right = mid - 1; // 如果不能，那么只能减少甜度。
            }
        }
        return ans;
    }

    public boolean check(int swt, int K, int[] s) { // 检查甜度是否符合
        int sum = 0, cur = 0;
        for (int x : s) { // 不停的放进去，贪心的去分，只要一符合条件，就切一刀。
            sum += x;
            if (sum >= swt) { // 如果分到这个发现甜度比mid大了，那么直接切一刀。
                ++cur; // 分到一块符合条件，+1.
                sum = 0; // 下一块又从0开始加了。
            }
        }
        return cur >= K;
    }
}