企业网站深圳,做网站的人月,长沙互联网大厂,广州建设网站外包本文涉及的基础知识点
C二分查找 贪心#xff08;决策包容性)
LeetCode 2517. 礼盒的最大甜蜜度
给你一个正整数数组 price #xff0c;其中 price[i] 表示第 i 类糖果的价格#xff0c;另给你一个正整数 k 。 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼…本文涉及的基础知识点
C二分查找 贪心决策包容性)
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 105 1 price[i] 109
C 二分查找贪心
将price按升序排序。本题的Check函数f(x)是否存在某种方案甜蜜度大于等于x。 ⟺ \iff ⟺ price中任意选择k个元素两两差的绝对值 x。 性质一某合法方案如果不包括min(price)则将已选择的糖果价格最低的换成min(price)仍然合法。 性质二如果选择的第i个第i1个糖果之间有价格 第i个糖果x,则用此糖果换第i1个糖果。 总结选择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]
代码
核心代码
templateclass INDEX_TYPE
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}templateclass _PrINDEX_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;}templateclass _PrINDEX_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(vectorint 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 CBinarySearchint(0, 1e9).FindEnd(Check);}};单元测试
vectorint price;int k;TEST_METHOD(TestMethod1){price { 1,1000000000 }, k 2;auto res Solution().maximumTastiness(price, k);AssertEx(999999999, 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);}扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
