【C++二分查找】2517. 礼盒的最大甜蜜度

本文涉及的基础知识点

LeetCode 2517. 礼盒的最大甜蜜度

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。
商店组合 k 类不同糖果打包成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖果价格绝对差的最小值。
返回礼盒的最大甜蜜度。
示例 1：
输入：price = [13,5,1,8,21,2], k = 3
输出：8
解释：选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。
示例 2：

输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。
示例 3：

输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

提示：
2 <= k <= price.length <= 10⁵
1 <= price[i] <= 10⁹

C++ 二分查找+贪心

将price按升序排序。本题的Check函数f(x)：是否存在某种方案甜蜜度大于等于x。 $\iff$ price中任意选择k个元素，两两差的绝对值 >= x。
性质一：某合法方案如果不包括min(price)，则将已选择的糖果价格最低的换成min(price)，仍然合法。
性质二：如果选择的第i个，第i+1个糖果之间有价格>= 第i个糖果+x,则用此糖果换第i+1个糖果。
总结：选择min(price)后，按性质三选择，简称g(x)。
f(x) $\rightarrow$ g(x) ；g(x)的方案符合题意，故g(x) $\rightarrow$ f(x)。即f(x) $\iff$ g(x)。
本题的解f(x)的最大解，即g(x)的最大解也是本题答案。
二分类型：寻找尾端。
Check函数的参数范围：[0,1e9]

代码

核心代码

template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist( _Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd( _Pr pr){int leftInclude = m_iMin;int right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {public:int maximumTastiness(vector<int>& price, int k) {sort(price.begin(), price.end());auto Check = [&](int mid) {int pre = price.front();int cnt = k - 1;for (int i = 1; (i < price.size())&& cnt ; i++) {if (price[i] >= mid + pre) {cnt--;pre = price[i];}}return 0 == cnt;};return CBinarySearch<int>(0, 1e9).FindEnd(Check);}};

单元测试

vector<int> price;int k;TEST_METHOD(TestMethod1){price = { 1,1000'000'000 }, k = 2;auto res = Solution().maximumTastiness(price, k);AssertEx(999'999'999, res);}TEST_METHOD(TestMethod11){price = { 13, 5, 1, 8, 21, 2 }, k = 3;auto res = Solution().maximumTastiness(price, k);AssertEx(8, res);}TEST_METHOD(TestMethod12){price = { 1,3,1 }, k = 2;auto res = Solution().maximumTastiness(price, k);AssertEx(2, res);}TEST_METHOD(TestMethod13){price = { 7,7,7,7 }, k = 2;auto res = Solution().maximumTastiness(price, k);AssertEx(0, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功