LeetCode 1231. 分享巧克力（极小极大化二分查找）

84 阅读 0 评论 56 点赞

我是靠谱客的博主淡然大地，最近开发中收集的这篇文章主要介绍LeetCode 1231. 分享巧克力（极小极大化二分查找），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

- 1. 题目
- 2. 解题

1. 题目

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

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

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

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

示例 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(vector<int>& sweetness, int K) {
    	int l = 0, r = 1e9, mid, ans=0;
        K++;//包含自己
    	while(l <= r)
    	{
    		mid = l+((r-l)>>1);
    		if(!cansplitK(sweetness, mid,K))
    			r = mid-1;
    		else
    			ans = mid, l = mid+1;
    	}
    	return ans;
    }
    bool cansplitK(vector<int>& 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;
    }
};