---

1231. 分享巧克力

• 标签：数组、二分查找
• 难度：困难

题目链接

• 1231. 分享巧克力 - 力扣

题目大意

描述：你有一大块巧克力，由一些甜度不完全相同的小块组成，用数组 $sweetness$ 表示每一小块的甜度。你打算和 $K$ 名朋友一起分享，所以你需要将巧克力切割 $K$ 次得到 $K+1$ 块，每一块都由一些连续的小块组成。你将会吃掉总甜度最小的一块，其余分给朋友们。

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

说明：

• $0 \le K \lt sweetness.length \le 10^4$。
• $1 \le sweetness[i] \le 10^5$。

示例：

• 示例 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 块。

解题思路

思路 1：二分查找答案

1. 核心思想

遇到「最大化最小值」或「最小化最大值」的问题，通常可以用二分答案来解决。

我们不是直接找切割方案，而是猜测一个答案 $mid$，然后判断：能否切出至少 $K+1$ 块，使得每块的甜度都 $\ge mid$？

如果能，说明 $mid$ 可行，我们尝试更大的值（往右半边找）。如果不能，说明 $mid$ 太大了，需要减小（往左半边找）。

这种「猜答案 + 验证」的思路之所以高效，是因为验证函数（判断能否切出至少多少块）通常可以用贪心 $O(n)$ 实现，比直接求最优解容易得多。

2. 具体步骤

第 1 步：确定二分范围

• 下界 $left$：每块的最小甜度至少为 $1$（因为 $sweetness[i] \ge 1$）。
• 上界 $right$：最理想情况是所有块甜度均分，即 $\frac{sum(sweetness)}{K+1}$。不可能超过这个值，因为总甜度固定。

第 2 步：定义检查函数 $can\_divide(mid)$

贪心地从左到右切分：

• 维护当前块的累加甜度 $cur$ 和已切出的块数 $cnt$。
• 遍历每个小块，累加到 $cur$。
• 当 $cur \ge mid$ 时，说明当前块已经达到目标甜度，切出一块（$cnt += 1$），并重置 $cur = 0$。
• 遍历结束后，如果 $cnt \ge K+1$，返回 True，否则返回 False。

第 3 步：二分查找

使用左闭右开或左闭右闭的二分模板。这里使用「找最大值」模板：

• 当 $can\_divide(mid)$ 为 True 时，$left = mid$（尝试更大的值）。
• 否则 $right = mid - 1$。
• 注意 $mid$ 取 $(left + right + 1) // 2$（向上取整），防止死循环。

结合示例 1 走一遍：

$sweetness = [1,2,3,4,5,6,7,8,9], K = 5$，需要 $K+1 = 6$ 块。

总甜度 $= 45$，$right = 45 // 6 = 7$，$left = 1$。

检查 $mid = (1 + 7 + 1) // 2 = 4$：

• 遍历：$1+2=3<4$，$+3=6\ge4$ 切一块；$4<4$，$+5=9\ge4$ 切一块；$6\ge4$ 切一块；$7\ge4$ 切一块；$8\ge4$ 切一块；$9\ge4$ 切一块。共 $7$ 块 $\ge 6$ → 可行，$left=4$。

检查 $mid = (4 + 7 + 1) // 2 = 6$：

• 遍历：$1+2+3=6\ge6$ 切一块；$4+5=9\ge6$ 切一块；$6\ge6$ 切一块；$7\ge6$ 切一块；$8\ge6$ 切一块；$9\ge6$ 切一块。共 $6$ 块 $\ge 6$ → 可行，$left=6$。

检查 $mid = (6 + 7 + 1) // 2 = 7$：

• 遍历：$1+2+3+4=10\ge7$ 切一块；$5+6=11\ge7$ 切一块；$7\ge7$ 切一块；$8\ge7$ 切一块；$9\ge7$ 切一块。共 $5$ 块 $< 6$ → 不可行，$right=6$。

$left = right = 6$，返回 $6$。

3. 为什么贪心检查是正确的

从左到右切分时，只要累加甜度达到 $mid$ 就立刻切一刀，这种策略能最大化切出的块数。因为推迟切分只会让当前块更大，而不会帮助后面的块更容易达到 $mid$。所以贪心检查得到的是「最多能切出多少块 $\ge mid$ 的块」，如果这个最大值都达不到 $K+1$，那任何其他切法也达不到。

思路 1：代码

class Solution:
    def maximizeSweetness(self, sweetness: List[int], K: int) -> int:
        # 检查能否切出至少 K+1 块，每块甜度 >= mid
        def can_divide(mid):
            cur = 0   # 当前块的累加甜度
            cnt = 0   # 已切出的块数
            for s in sweetness:
                cur += s
                if cur >= mid:
                    cnt += 1
                    cur = 0
            return cnt >= K + 1

        # 二分范围的下界和上界
        left = 1
        right = sum(sweetness) // (K + 1)

        # 二分查找最大值
        while left < right:
            mid = (left + right + 1) // 2
            if can_divide(mid):
                left = mid
            else:
                right = mid - 1

        return left

思路 1：复杂度分析

• 时间复杂度：$O(n \log S)$，其中 $n$ 是数组 $sweetness$ 的长度，$S$ 是甜度总和。二分次数为 $O(\log S) \approx O(\log (n \times 10^5))$，每次检查需要 $O(n)$ 遍历数组。
• 空间复杂度：$O(1)$，只使用了常数个变量，没有额外空间开销。