题目描述

你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。

你打算和 K 名朋友一起分享这块巧克力，所以你需要将切割 K 次才能得到 K+1 块，每一块都由一些 连续 的小块组成。

为了表现出你的慷慨，你将会吃掉 总甜度最小 的一块，并将其余几块分给你的朋友们。

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

样例

输入：sweetness = [1,2,3,4,5,6,7,8,9], K = 5
输出：6
解释：你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。

输入：sweetness = [5,6,7,8,9,1,2,3,4], K = 8
输出：1
解释：只有一种办法可以把巧克力分成 9 块。

输入：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

算法

(二分答案 + 贪心) $O(n \times S)$

1. 这道题最终的答案具有单调性：即如果一个较大的甜度可以满足，则所有较小的甜度都可以满足。所以我们可以通过二分查找这个最大可以满足的甜度。
2. 二分的区间为 [0, S]，其中 S 为总甜度之和。
3. 对于一个甜度 mid，我们通过贪心判定是否符合切割条件。遍历甜度数组，如果当前连续的一段甜度值之和大于等于了 mid，则可切割的个数加 1。最后如果可切割的次数大于等于 K + 1，则说明可以分割。
4. 贪心的原理很简单，保证正确性的关键是在于要求分隔 连续 的一段。

时间复杂度

• 每次判定需要 $O(n)$ 的时间复杂度，故总时间复杂度为 $O(n \log S)$。

空间复杂度

• 只需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool check(int mid, const vector<int> &sweetness, int K) {
        int sum = 0, cnt = 0, n = sweetness.size();
        for (int i = 0; i < n; i++) {
            sum += sweetness[i];
            if (sum >= mid) {
                sum = 0;
                cnt++;
                if (cnt >= K)
                    return true;
            }
        }
        return false;
    }

    int maximizeSweetness(vector<int>& sweetness, int K) {
        int n = sweetness.size();
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += sweetness[i];

        K++;
        int l = 0, r = sum;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid + 1, sweetness, K)) l = mid + 1;
            else r = mid;
        }

        return l;
    }
};