题目大意：
你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1231
解题思路分析：
这是一道Hard级别的题目，一开始想到使用DP或者递归加记忆数组的方式解题，结果TLE超时。超时的原因在于本题的数据规模比较大，不适于使用动态规划（如果数据量小一些，DP应该是可行的）。后来想到了二分查找。本题的思路其实有些类似于之前讲过的一道题目：LEETCODE 1201. Ugly Number III 解题思路分析。
二分查找本身并不难，但难点在于如何二分。先看题目，我们要把一个巧克力分成N份（N等于K+1），然后将其中甜度最小的一份M分给自己。也就是说，这N份巧克力的甜度肯定都是大于等于M的。因此这道题可以转化为，我们能否找到一个最大的M，使得能够将巧克力分成N份，并且每一份的甜度都大于等于M。M的取值范围在0到总甜度和之间，利用二分查找能够最高效的找到最大的M值。
看下实现代码：
public int maximizeSweetness(int[] sweetness, int K) {
// 定义二分查找使用的左右指针
// 初始时左指针为sweetness中最小值，
// 右指针为sweetness之和
int right=0,left=Integer.MAX_VALUE;
for(int sweet : sweetness){
right+=sweet;
left=Math.min(left, sweet);
}
int res=0; // 返回结果
while(left<right){ // 开始二分查找
int mid=(left+right)/2; // 中间值
int sum=0; // 当前份的甜度和
int count=0; // 已分完的份数
int min=Integer.MAX_VALUE; // 最小甜度
// 从头开始循环每一块巧克力
for(int i=0;i<sweetness.length;i++){
// 累加当前份的甜度和
sum+=sweetness[i];
// 当甜度和大于等于mid时，代表可以分出一份
if(sum>=mid){
// 更新甜度最小的那一份
min=Math.min(min, sum);
// 如果已经分出了K+1份，说明当前mid这个甜度是可行的
// （剩下没分的部分可以分给任何一份）
if(++count==K+1){
// 更新最大的返回结果
res=Math.max(res, min);
break; // 退出
}
sum=0; // 重置sum，为了计算下一份的甜度和
}
}
// 如果当前mid是可行的（K+1份的甜度都大于等于mid）
// 说明可以适当加大mid，看看是否还可行
if(count==K+1){
left=mid+1;
}else{ // 反之减小mid找合理解
right=mid;
}
}
return res;
}本解法运行时间为10ms。
Runtime: 10 ms, faster than 30.39% of Java online submissions for Divide Chocolate.
Memory Usage: 40.1 MB, less than 100.00% of Java online submissions for Divide Chocolate.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1231-divide-chocolate-解题思路分析/