【C++二分查找】2517. 礼盒的最大甜蜜度
本文涉及的基础知识点
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个,第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);}

扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
| 学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
| 有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙,那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:
【C++二分查找】2517. 礼盒的最大甜蜜度
本文涉及的基础知识点 C二分查找 贪心(决策包容性) LeetCode 2517. 礼盒的最大甜蜜度 给你一个正整数数组 price ,其中 price[i] 表示第 i 类糖果的价格,另给你一个正整数 k 。 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼…...
【详解】数据库E-R图——医院计算机管理系统
题目 某医院病房计算机管理中需要如下信息: 科室:科室名,科室地址,科室电话,医生姓名 病房:病房号,床位号,所属科室名 医生:工作证号,姓名,性别&a…...
分类预测|基于改进的灰狼IGWO优化支持向量机SVM的数据分类预测matlab程序 改进策略:Cat混沌与高斯变异
分类预测|基于改进的灰狼IGWO优化支持向量机SVM的数据分类预测matlab程序 改进策略:Cat混沌与高斯变异 文章目录 一、基本原理原理流程1. **定义目标函数**2. **初始化GWO**3. **评估适应度**4. **更新狼的位置**5. **更新狼的等级**6. **重复迭代**7. **选择最佳解…...
圆锥曲线练习
设 A ( x 1 , y 1 ) , B ( x 2 , y 2 ) A\left( x_{1}, y_{1} \right), B\left( x_{2}, y_{2} \right) A(x1,y1),B(x2,y2) l : y k ( x 2 ) l: y k\left( x2 \right) l:yk(x2) 显然 y 0 y0 y0符合题意 当 k ≠ 0 k\neq 0 k0 联立 l l l和 C C C ( k 2 1 2 ) x…...
STM32时钟树
1 什么是时钟 2 时钟数简图...
NX—UI界面生成的文件在VS上的设置
UI界面保存生成的三个文件 打开VS创建项目,删除自动生成的cpp文件,将生成的hpp和cpp文件拷贝到项目的目录下,并且在VS项目中添加现有项目。 修改VS的输出路径,项目右键选择属性,链接器中的常规,文件路径D:…...
Wine容器内程序执行sh脚本问题研究
问题背景 wpf程序在wine环境执行sh脚本,不能等待脚本执行完成自动退出的问题进行了研究,需求很简单,在wpf程序使用cmd,或者bat ,又或者是直接执行sh脚本,想到脚本执行完成才处理后面的逻辑。但是实际验证过…...
《深度学习》OpenCV轮廓检测 模版匹配 解析及实现
目录 一、模型匹配 1、什么是模型匹配 2、步骤 1)提取模型的特征 2)在图像中查找特征点 3)进行特征匹配 4)模型匹配 3、参数及用法 1、用法 2、参数 1)image:待搜索对象 2)templ&am…...
Java XML
1、XML文件介绍 配置文件:用来保存设置的一些东西。 拿IDEA来举例,比如设置的背景图片,字体信息,字号信息和主题信息等等。 (1)以前是用txt保存的,没有任何优点,而且不利于阅读&a…...
好用的视频压缩工具有哪些?这4款千万不要错过
视频压缩的方法有很多种,像我们手机里的视频剪辑工具,手机和电脑自带的压缩功能,在线压缩网站,专业压缩软件压缩等等。不同的场景和需求下大家可以选择不同的工具,但是如果碰到需要大量和经常压缩视频的话,…...
【Python爬虫系列】_016.关于登录和验证码
我 的 个 人 主 页:👉👉 失心疯的个人主页 👈👈 入 门 教 程 推 荐 :👉👉 Python零基础入门教程合集 👈👈 虚 拟 环 境 搭 建 :👉&…...
基于opencv实现双目立体匹配点云距离
双目相机或两个单目相机。 一、相机标定 MATLAB软件,打开双目标定app。 点击add images,弹出加载图像的窗口,分别导入左图和右图,设置黑白格长度(标定板的长度一般为20)。 点击确定,弹出加载…...
RabbitMQ高级篇,进阶内容
强烈建议在看本篇博客之前快速浏览文章:RabbitMQ基础有这一篇就够了 RabbitMQ高级篇 0. 前言1. 发送者的可靠性1.1 生产者重试机制1.2 生产者确认机制1.3 实现生产者确认 2. MQ的可靠性2.1 MQ持久化2.2 LazyQueue 3. 消费者的可靠性3.1 消费者确认机制3.2 失败重试策…...
STM32重定义printf,实现串口打印
在“usart.c”文件中加入以下代码 #ifdef __GNUC__#define PUTCHAR_PROTOTYPE int __io_putchar(int ch) #else#define PUTCHAR_PROTOTYPE int fputc(int ch, FILE *f) #endifPUTCHAR_PROTOTYPE{HAL_UART_Transmit(&huart1 , (uint8_t *)&ch, 1, 0xFFFF);return ch; }…...
项目进度
变为负进度了,还是要用baseservlet,我就又重新写了一部分,看了好几遍视频,突然就想明白了,感觉每次要上课,就时间不连续思路总是断,今天晚自习算是搞懂了怎么写了,就是代码有点多&am…...
Android的内核
Android的内核是基于Linux的长期支持版本的“Android通用内核(ACK)”。 Android作为一个广泛使用的操作系统,其根基在于内核的设计和功能。下面将深入探讨Android内核的各个方面,从其基本结构到与Linux内核的关系,再到内核的版本管理及在设备…...
Github Wiki 超链接 转 码云Gitee Wiki 超链接
Github Wiki 超链接 转 码云Gitee Wiki 超链接 Github 是 :[[相对路径]] Gitee 是 :[链接文字](./相对路径) 查找:\[\[(.*?)\]\] 替换:[$1]\(./$1\) 或替换:**[$1]\(./$1\)** (码云的超链接,很…...
Android10源码刷入Pixel2以及整合GMS
一、ASOP源码下载 具体可以参考我之前发布的文章 二、下载相关驱动包 这一步很关键,关系到编译后的镜像能否刷入后运行 下载链接:Nexus 和 Pixel 设备的驱动程序二进制文件 如下图所示,将两个驱动程序上传到Ubuntu服务器,并进行解压,得到两个脚本: 下载解压后会有两…...
wpf触发与模板的使用示例:批量生产工具
批量生产工具 <Window x:Class"WpfM20UpdateFW.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/expressio…...
brew install node提示:Error: No such keg: /usr/local/Cellar/node
打开本地文件发现Cellar目录下无法生成 node文件,应该是下载时出现问题,重复下载无法解决问题,只能重新安装brew。 步骤1(安装 brew): /bin/zsh -c “$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/ra…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...
上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式
简介 在我的 QT/C 开发工作中,合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式:工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...
