泉州模板建站平台,台州seo网站管理,网站建设与维护试卷,安县网站制作文章目录1. 题目2. 解题1. 题目
你有一大块巧克力#xff0c;它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。
你打算和 K 名朋友一起分享这块巧克力#xff0c;所以你需要将切割 K 次才能得到 K1 块#xff0c;每一块都由一些 连续 的小…
文章目录1. 题目2. 解题1. 题目
你有一大块巧克力它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。
你打算和 K 名朋友一起分享这块巧克力所以你需要将切割 K 次才能得到 K1 块每一块都由一些 连续 的小块组成。
为了表现出你的慷慨你将会吃掉 总甜度最小 的一块并将其余几块分给你的朋友们。
请找出一个最佳的切割策略使得你所分得的巧克力 总甜度最大并返回这个 最大总甜度。
示例 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 块。示例 3
输入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来源力扣LeetCode 链接https://leetcode-cn.com/problems/divide-chocolate 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 410. 分割数组的最大值极小极大化 二分查找 LeetCode 668. 乘法表中第k小的数二分查找 LeetCode 774. 最小化去加油站的最大距离极小极大化 二分查找 LeetCode 875. 爱吃香蕉的珂珂二分查找 LeetCode LCP 12. 小张刷题计划二分查找 LeetCode 1011. 在 D 天内送达包裹的能力二分查找 LeetCode 1102. 得分最高的路径优先队列BFS/极大极小化 二分查找 LeetCode 1062. 最长重复子串二分查找 LeetCode 5438. 制作 m 束花所需的最少天数二分查找 LeetCode 5489. 两球之间的磁力极小极大化 二分查找 LeetCode 5548. 最小体力消耗路径DFS 二分查找 LeetCode 1760. 袋子里最少数目的球二分查找 LintCode 1816. 使结果不超过阈值的最小除数二分查找 LeetCode 5739. 最高频元素的频数二分查找 LeetCode 5764. 准时到达的列车最小时速二分查找
class Solution {
public:int maximizeSweetness(vectorint sweetness, int K) {int l 0, r 1e9, mid, ans0;K;//包含自己while(l r){mid l((r-l)1);if(!cansplitK(sweetness, mid,K))r mid-1;elseans mid, l mid1;}return ans;}bool cansplitK(vectorint sweet, int s, int K){int people 0, total 0;for(int i 0; i sweet.size(); i){total sweet[i];if(total s){people;total 0;if(people K)return true;}}return people K;}
};56 ms 14.7 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
