题目
你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组 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$
分析
我们要分配蛋糕，在能够分完的前提下，甜度最小的蛋糕的甜度要尽可能的大。本质就是：分配数组的排序中，将最小值逐渐调整到最大。二分调整，并尝试。
我们尝试分配蛋糕，不难得出：
- 甜度平均值是理论的分配的甜度最小块的最大甜度。
- 解释：所有人
- 甜度的下限是当前甜度的最小值。
按照上述区间进行二分蛋糕分配：
- 二分平均取目标甜度的值
- 尝试分配蛋糕
- 甜度超过二分分值，重新分配给下个人，
- 直到蛋糕分配完成
- 当前分配方案已经覆盖了所有人，仍有剩余，则说明我们的甜度值小了，增大二分左边界
- 当前分配方案没有覆盖所有人，有的人没有蛋糕，说明我们的甜度值大了，减小二分右边界
- 最后二分搜索退出，
l==r随便返回一个值
解法
class Solution {
public int maximizeSweetness(int[] sweetness, int k) {
int nP = k + 1;// k个小朋友，和一个自己
Arrays.sort(sweetness);
int l = Arrays.stream(sweetness).min().getAsInt();// 最小值
int r = Arrays.stream(sweetness).sum() / nP;// 平均值
while (l < r) {
// 开启新一轮蛋糕划分
int mid = (l + r + 1)/2;
int curS = 0;// 每个人划分到的蛋糕的当前值
int pC = 0;// 分配到蛋糕的人数
// 尝试分配，得到pC
for (int s : sweetness) {
curS += s;// 甜度为s的蛋糕分配一下
// 达到最大甜度了
if (curS >= mid) {
pC++;// 已经分配的人头计数
curS = 0;// 换下一个人
}
}
// 蛋糕太多了，增大左侧，增大mid值
if (pC >= nP) {
l = mid;
} else {
// 蛋糕不够分了，减小右侧，减小mid
r = mid - 1;
}
}
return r;
}
}
总结
本题经过分析后，将问题抽象成一个二分搜索题。二分搜索中，我们通过计算pC来作为二分边界更新的依据。这种属于二分搜索中的构造特殊二分判断边界更新依据。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
