LeetCode 1231. 分享巧克力

2023-08-09 HGNULB 约 12 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 1231. 分享巧克力

题意分析

一排巧克力，第 i 块的甜度是 sweetness[i]。要沿着若干条缝把它切成连续的若干段，分给 k 位朋友和自己，也就是恰好切成 k + 1 段。自己会拿到甜度总和最小的那一段，问这个最小段的甜度最大能是多少。

第一件要看清的事：切分是连续区间的划分，不能重排、不能挑着拿。所以一个划分方案完全由 k 条切缝的位置决定，方案数是 $\binom{n-1}{k}$，直接枚举是组合爆炸。

第二件事是目标函数的形态：「最大化各段和的最小值」。这是典型的极小极大结构，它有一个非常有用的性质——把目标值本身拿出来当作候选来判定，往往比直接构造最优方案容易得多。具体说，「能否切出 k + 1 段，使每段和都至少为 x」这个判定问题，比「最优的 x 是多少」好回答。

第三件事是单调性。如果每段至少 x 能做到，那么每段至少 x - 1 显然也能做到（同一个方案就满足）；反过来 x 做不到，比 x 更大的值更做不到。所以可行的 x 构成一个从 1 开始的连续前缀，答案就是这个前缀的最后一个元素。「判定容易 + 可行性单调」，这两条凑齐就是二分答案。

约束方面：sweetness[i] ≥ 1 保证了任何一段的和都是正数，答案下界是 1；n ≤ 10^4、单个甜度 $\le 10^9$ 时总和可能达到 $10^{13}$，但由于答案上界是 total / (k + 1) 且题目实际数据规模较小，用 32 位整型存和是安全的——不过累加时仍要留意量级。

边界：k = 0 时不切，答案就是全部甜度之和；k + 1 == n 时每块自成一段，答案是数组最小值。这两种极端都应该被主逻辑自然覆盖，不需要特判。

解法：二分最小甜度 + 贪心切分

核心思路

暴力做法是枚举所有切法：从 n - 1 条缝里选 k 条，对每种方案求各段和的最小值，取全局最大。瓶颈是方案数呈组合级增长，n = 10^4 时完全不可行。换成区间 DP（dp[i][j] 表示前 i 块切成 j 段的最大最小值）能降到多项式，但那是 $O(n^2 k)$，仍然过不了。

观察：我们真正需要的不是「构造出最优方案」，而是「确定最优值」。于是把问题反过来问——给定一个甜度门槛 x，最多能切出多少段每段和都 $\ge x$ 的连续段？ 记这个最大段数为 g(x)。那么「x 可行」等价于 g(x) >= k + 1（多切出来的段可以合并到相邻段里，只会让段和更大，仍然满足门槛）。

g(x) 怎么算？贪心：从左往右累加，一旦累计和达到 x 就立刻切一刀并清零。这个贪心为什么最优——用交换论证：设最优切法的第一刀在位置 p，而贪心的第一刀在位置 q，由贪心「一达标就切」可知 $q \le p$。把最优方案的第一刀从 p 提前到 q，第一段仍然达标（贪心保证了 $[0, q]$ 的和 $\ge x$），而剩余部分变得更长、包含的元素是原剩余部分的超集，所以后面能切出的段数不会减少。逐刀替换下去，贪心的段数不劣于任何方案，故它就是 g(x)。

又因为 x 增大时每段需要吃掉更多元素，段数只会减少或不变，所以 g(x) 关于 x 单调不增，判定 g(x) >= k + 1 的真值随 x 增大从真变假且只变一次。这正是二分「最后一个可行值」的标准场景。

二分不变量：区间 [left, right] 始终满足「left 可行」且「right + 1 不可行」，即答案恒在区间内。每轮取 mid：若 mid 可行，答案至少是 mid，收缩为 [mid, right]（注意是 left = mid 而不是 mid + 1，因为 mid 自己可能就是答案）；否则收缩为 [left, mid - 1]。

因为存在 left = mid 这个分支，mid 必须用偏右中点 left + (right - left + 1) / 2。否则当区间只剩两个数时 mid 恒等于 left，可行分支下区间原地不动，直接死循环。

区间的上界取 total / (k + 1)：k + 1 段的和加起来等于 total，最小段不可能超过平均值。下界取 1，因为所有甜度都是正整数。

解题步骤

先求总和并令 requiredPieces = k + 1。为什么是 k + 1 而不是 k：k 个朋友加上自己，一共 k + 1 个人，每人一段。这是本题最高频的读题错误，写代码前先把这个数算准。

确定二分区间 [1, total / requiredPieces]。下界 1 的依据是甜度均为正整数，最小段至少是 1。上界取平均值的依据是抽屉原理：requiredPieces 段的和恰为 total，最小段不可能大于平均值。为什么不能用数组最大值当上界：sweetness = [1, 100]、k = 1 时最大值是 100，但答案只能是 1，用 100 当上界虽然不会算错（二分会收敛回来），却在 k 很大时白白多做几轮；更糟的是有人会误用数组最小值当上界，那会直接把正确答案排除在区间外。

二分主体用「找最后一个可行值」的模板：while (left < right)，mid = left + (right - left + 1) / 2，可行则 left = mid，否则 right = mid - 1。为什么中点必须偏右：只有偏右才能保证 mid > left，让 left = mid 这个分支真正推进区间，避免死循环。

判定函数贪心切分：累加当前段的和，一旦 >= minSweetness 就 pieces++ 并把累加器清零。为什么是「达标立刻切」而不是「多攒一点再切」：多攒的部分对当前段毫无价值（当前段已经达标了），却减少了后面可用的元素，只会让总段数变少或不变。

判定条件写 pieces >= requiredPieces 而非 ==。为什么允许切多：切出的多余段可以随意并入相邻段，合并只会增大段和，门槛依然满足，所以「能切出更多段」同样说明 x 可行。写成 == 会把大量可行值误判为不可行，答案偏小。

末尾的残料直接丢弃。循环结束时累加器里可能还剩一段不足 x 的尾巴，不计入 pieces。为什么可以丢：这段尾巴会被合并进前一段，前一段本来就达标，加上非负的尾巴后依然达标，不影响判定结果。

返回 left：循环退出时 left == right，由不变量可知它就是最大的可行值。

以 sweetness = [1, 2, 3, 4, 5, 6, 7, 8, 9]、k = 5 走一遍（答案是 6）。

requiredPieces = 6，total = 45，区间初始为 [1, 45 / 6] = [1, 7]。

第一轮：mid = 1 + (7 - 1 + 1) / 2 = 4。贪心判定 x = 4：累加 1+2+3=6 ≥ 4 切第一段（pieces = 1）；4 ≥ 4 切（2）；5 ≥ 4 切（3）；6 切（4）；7 切（5）；8 切（6）；9 切（7）。pieces = 7 ≥ 6，可行，left = 4，区间 [4, 7]。注意这里切出了 7 段而不是恰好 6 段，多出来的一段合并回去即可，判定仍然成立。

第二轮：mid = 4 + (7 - 4 + 1) / 2 = 6。判定 x = 6：1+2+3=6 切（1）；4+5=9 ≥ 6 切（2）；6 切（3）；7 切（4）；8 切（5）；9 切（6）。pieces = 6 ≥ 6，可行，left = 6，区间 [6, 7]。

第三轮：mid = 6 + (7 - 6 + 1) / 2 = 7。判定 x = 7：1+2+3+4=10 ≥ 7 切（1）；5+6=11 切（2）；7 切（3）；8 切（4）；9 切（5）。pieces = 5 < 6，不可行，right = 6。

此时 left == right == 6，返回 6。对应的切法是 [1,2,3] [4,5] [6] [7] [8] [9]，最小段恰为 6。

若这一轮把中点写成普通的 left + (right - left) / 2，区间 [6, 7] 会算出 mid = 6，可行后 left = 6，区间纹丝不动，程序永远跑不出这一轮——这就是偏右中点存在的唯一理由。

代码实现

class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        int requiredPieces = k + 1;
        int totalSweetness = 0;
        for (int value : sweetness) {
            totalSweetness += value;
        }

        int left = 1;
        int right = totalSweetness / requiredPieces;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (canSplit(sweetness, requiredPieces, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private boolean canSplit(int[] sweetness, int requiredPieces, int minSweetness) {
        int pieces = 0;
        int currentSweetness = 0;

        // 达到候选甜度就立刻切，才能给后面保留最多机会。
        for (int value : sweetness) {
            currentSweetness += value;
            if (currentSweetness >= minSweetness) {
                pieces++;
                currentSweetness = 0;
            }
        }

        return pieces >= requiredPieces;
    }
}

func maximizeSweetness(sweetness []int, k int) int {
    requiredPieces := k + 1
    totalSweetness := 0
    for _, value := range sweetness {
        totalSweetness += value
    }

    left := 1
    right := totalSweetness / requiredPieces
    for left < right {
        mid := left + (right-left+1)/2
        if canSplit(sweetness, requiredPieces, mid) {
            left = mid
        } else {
            right = mid - 1
        }
    }

    return left
}

func canSplit(sweetness []int, requiredPieces int, minSweetness int) bool {
    pieces := 0
    currentSweetness := 0

    // 达到候选甜度就立刻切，才能给后面保留最多机会。
    for _, value := range sweetness {
        currentSweetness += value
        if currentSweetness >= minSweetness {
            pieces++
            currentSweetness = 0
        }
    }

    return pieces >= requiredPieces
}

复杂度分析

时间复杂度：$O(n \log S)$，其中 n 是巧克力块数，$S = \text{total} / (k+1)$ 是答案的取值范围大小。凭什么：求总和是一次 $O(n)$ 扫描；二分把值域折半，轮数是 $O(\log S)$，每轮的贪心判定要完整扫一遍数组，是 $O(n)$，两者相乘即得。判定函数内部没有嵌套循环，累加与比较都是常数操作。

空间复杂度：$O(1)$。凭什么：只用了总和、左右边界、中点、段计数和累加器这几个标量，没有任何辅助数组，贪心判定也是流式扫描不需要缓存。

关键点总结

看到「最大化最小值」或「最小化最大值」，第一反应就是二分答案：把「求最优值」翻译成「判定某个值是否可行」，再验证可行性的单调性。这是 410、875、1011、1552 等一大类题的共同入口，面试时先说出这个识别信号再动笔。

二分答案的判定函数几乎总是贪心，且贪心的正确性要能用交换论证讲清楚——「把最优解的第一步替换成贪心的第一步，不会变差，归纳可得贪心最优」。能讲出这段论证，比写对代码更能拿分。

判定时用 >= 而不是 == 是通用规律：多切出来的段总能合并回去，所以「能做到更多」蕴含「能做到刚好」。凡是判定「至少 / 至多」的场景都要检查这个方向。

「找最后一个可行值」和「找第一个可行值」是两套模板，前者必须配偏右中点，后者用普通中点。把 left = mid 与 mid = left + (right - left + 1) / 2 绑定记忆，能杜绝一整类死循环。

二分区间的上下界要从题目结构推导而不是拍脑袋：本题上界来自抽屉原理（最小段 $\le$ 平均值），下界来自元素为正整数。界取宽只是多几轮，界取窄则会直接丢掉答案。

读题时先把「要切成几段」算准：k 个朋友对应 k + 1 段。计数类的差一错误比算法错误更常见，也更难在样例上被发现。

易错点总结

把段数写成 k 而不是 k + 1：sweetness = [1,2,3,4,5,6,7,8,9]、k = 5 时按 5 段判定会得到答案 9（切成 [1..4][5,6][7][8][9] 之类），而正确答案是 6，直接偏大。

判定写成 pieces == requiredPieces：上例中 x = 4 能切出 7 段，用 == 判定为不可行，二分立刻把区间压到 [1, 3]，最终返回 3。可行值被大面积误杀。

用普通中点却写 left = mid：区间收缩到 [6, 7] 且 6 可行时，mid 恒为 6，left 赋回 6，区间不再变化，程序死循环直至判题机超时——现象是 TLE 而非 WA，容易误以为是复杂度问题。

反过来用偏右中点却写 right = mid：不可行分支下 right 可能保持不变，同样死循环。中点偏向与哪个分支「原地赋值」必须严格配对。

二分上界取数组最大值：sweetness = [1, 100]、k = 1 时上界 100 虽仍能收敛，但若误取成数组最小值 1，区间变成 [1, 1]，sweetness = [5, 6, 7]、k = 0 这种答案为 18 的用例会直接返回 5。

二分下界取 0：x = 0 时贪心的 currentSweetness >= 0 在第一个元素处就成立，每个元素各成一段，pieces = n 恒可行，虽不影响最终收敛，但若判定函数写成 > 0 的变体就会出现除零或空段等混乱。

贪心切分后忘记把累加器清零：currentSweetness 一直累加，达到门槛后每个后续元素都会触发一次切割，sweetness = [1,1,1,1]、x = 2 会数出 3 段而不是 2 段，判定虚高，答案偏大。

把末尾残料也算作一段：sweetness = [5, 5, 1]、x = 5 时前两段各达标，剩下的 1 不足门槛却被计入，pieces 变成 3；k = 2 时会误判 5 可行，而真实答案是 1。

改成「攒够两倍再切」之类的保守贪心：sweetness = [1,2,3,4,5,6,7,8,9]、x = 6 时若非要攒到 12 才切，只能切出 3 段，判定为不可行，答案被压到 4 以下。贪心必须是「一达标立刻切」。

误以为要让每段甜度尽量接近平均值：sweetness = [9, 1, 1, 1, 9]、k = 1 时平均值是 10.5，但连续性约束下最优切法是 [9,1,1,1] [9]，最小段为 9；追求均分会切成 [9,1] [1,1,9] 得到 10 却只有两段中较小的 10……实际最优是 [9,1,1] [1,9] 得 10。关键在于必须保持连续，任何「排序后均分」的直觉都不成立。

相似题目

题目	难度	考察点
410. 分割数组的最大值	困难	镜像问题：最小化最大段和，判定改为「段数不超过 m」，二分方向相反
1011. 在 D 天内送达包裹的能力	中等	二分运载能力，判定是「天数不超过 D」，下界必须取单件最大重量而非 1
875. 爱吃香蕉的珂珂	中等	二分的是速度，判定用向上取整求和，不涉及连续段划分
1552. 两球之间的磁力	中等	同为「最大化最小值」，但对象是相邻间距，需先排序再贪心放球
1482. 制作 m 束花所需的最少天数	中等	二分天数，判定是扫描连续开花段并整除，展示了非求和型判定函数
774. 最小化去加油站的最大距离	困难	答案是实数，需要二分浮点数并控制精度轮数，判定用向上取整统计新增加油站