LeetCode 1231. 分享巧克力

2023-08-09 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 困难未解决会员题 2-5 美团百度

题目描述

✅ 1231. 分享巧克力

题意分析

给 k 个朋友和自己分巧克力，需要切成 k + 1 个非空连续段，每段甜度是其中元素之和。自己拿甜度最小的一段，要让这个最小值尽可能大。

直接枚举切点很难，但给定一个门槛 x 后，可以判断是否存在一种切法，让每段甜度都不少于 x。门槛越低越容易满足，适合二分答案。

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

核心思路

[!blue]

判定时从左到右累加甜度，一旦当前段达到 x 就立即切下，并从下一块重新累加。这样得到的第一段结束位置最早；任何满足门槛的切法，都不可能比它更早结束第一段。

把其他切法的第一刀提前到这个位置，只会给剩余部分留下更多正甜度，不会妨碍后面的段达标。对后续各段重复这个理由，就能说明“达标立即切”得到的达标段数最多。

若得到至少 k + 1 段，就可以保留前 k 段，把剩余所有内容并成最后一段。由于剩下至少还有一段已达标，合并多余段和不足门槛的尾部后仍然达标，所以判断条件是段数不少于要求，而不是恰好相等。

门槛 x 可行时，更低门槛也可行；不可行时，更高门槛也不可能可行。二分寻找最大的可行门槛：可行就令 left = mid，否则令 right = mid - 1。这里使用向上取整的中点，避免只剩两个候选值时左边界不动。

解题步骤

计算 requiredPieces = k + 1 和甜度总和。所有甜度均为正数，下界可以取 1；最小段和不会超过平均值，所以上界取 totalSweetness / requiredPieces。

取偏右中点 mid，从头扫描，用 pieces 记录已经切出的达标段数，用 currentSweetness 记录尚未切下的当前段。

当前段达到 mid 时，让 pieces 加一并把累计甜度清零，最后判断是否有足够段数。

按判定结果缩小区间，直到 left == right，返回最大可行门槛。

k = 0 时整块都归自己，答案是总甜度；需要给每个小块单独分段时，答案是最小元素，两种情况都由同一判定处理。

代码实现

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+1))$，S 为总和除以所需段数。

空间复杂度：$O(1)$。

关键点总结

[!green]

要求 k 个朋友加自己，共 k+1 段。

达标立即切证明依赖甜度非负。

易错点总结

[!yellow]

只接受段数恰好相等，会误拒可以合并的多段方案。

切完不清零，会把已经用过的甜度重复计入。

用数组最大值作上界，可能小于多块组成一段的最优甜度。

相似题目

题目	难度	关联与区别
410. 分割数组的最大值	困难	同样按连续分段二分阈值，但本题最大化最小段和，原题最小化最大段和，贪心判定方向相反。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/48400132

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！