题目描述
你有一大块巧克力,它由一些甜度不完全相同的小块组成。我们用数组 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)$
- 这道题最终的答案具有单调性:即如果一个较大的甜度可以满足,则所有较小的甜度都可以满足。所以我们可以通过二分查找这个最大可以满足的甜度。
- 二分的区间为
[0, S]
,其中S
为总甜度之和。 - 对于一个甜度
mid
,我们通过贪心判定是否符合切割条件。遍历甜度数组,如果当前连续的一段甜度值之和大于等于了mid
,则可切割的个数加 1。最后如果可切割的次数大于等于K + 1
,则说明可以分割。 - 贪心的原理很简单,保证正确性的关键是在于要求分隔 连续 的一段。
时间复杂度
- 每次判定需要 $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;
}
};
非常感谢,acwing可以打赏吗?
为什么check 第一个参数是
mid + 1
而不是mid
这是因为如果
mid + 1
符合条件,我们才可以移动左边界到l + 1
。我这里的二分区间划分是[l, mid]
与[mid + 1, r]