当前位置: 首页 > news >正文

【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二分查找 贪心&#xff08;决策包容性) LeetCode 2517. 礼盒的最大甜蜜度 给你一个正整数数组 price &#xff0c;其中 price[i] 表示第 i 类糖果的价格&#xff0c;另给你一个正整数 k 。 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼…...

【详解】数据库E-R图——医院计算机管理系统

题目 某医院病房计算机管理中需要如下信息&#xff1a; 科室&#xff1a;科室名&#xff0c;科室地址&#xff0c;科室电话&#xff0c;医生姓名 病房&#xff1a;病房号&#xff0c;床位号&#xff0c;所属科室名 医生&#xff1a;工作证号&#xff0c;姓名&#xff0c;性别&a…...

分类预测|基于改进的灰狼IGWO优化支持向量机SVM的数据分类预测matlab程序 改进策略:Cat混沌与高斯变异

分类预测|基于改进的灰狼IGWO优化支持向量机SVM的数据分类预测matlab程序 改进策略&#xff1a;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 k0 联立 l l l和 C C C ( k 2 1 2 ) x…...

STM32时钟树

1 什么是时钟 2 时钟数简图...

NX—UI界面生成的文件在VS上的设置

UI界面保存生成的三个文件 打开VS创建项目&#xff0c;删除自动生成的cpp文件&#xff0c;将生成的hpp和cpp文件拷贝到项目的目录下&#xff0c;并且在VS项目中添加现有项目。 修改VS的输出路径&#xff0c;项目右键选择属性&#xff0c;链接器中的常规&#xff0c;文件路径D:…...

Wine容器内程序执行sh脚本问题研究

问题背景 wpf程序在wine环境执行sh脚本&#xff0c;不能等待脚本执行完成自动退出的问题进行了研究&#xff0c;需求很简单&#xff0c;在wpf程序使用cmd&#xff0c;或者bat &#xff0c;又或者是直接执行sh脚本&#xff0c;想到脚本执行完成才处理后面的逻辑。但是实际验证过…...

《深度学习》OpenCV轮廓检测 模版匹配 解析及实现

目录 一、模型匹配 1、什么是模型匹配 2、步骤 1&#xff09;提取模型的特征 2&#xff09;在图像中查找特征点 3&#xff09;进行特征匹配 4&#xff09;模型匹配 3、参数及用法 1、用法 2、参数 1&#xff09;image&#xff1a;待搜索对象 2&#xff09;templ&am…...

Java XML

1、XML文件介绍 配置文件&#xff1a;用来保存设置的一些东西。 拿IDEA来举例&#xff0c;比如设置的背景图片&#xff0c;字体信息&#xff0c;字号信息和主题信息等等。 &#xff08;1&#xff09;以前是用txt保存的&#xff0c;没有任何优点&#xff0c;而且不利于阅读&a…...

好用的视频压缩工具有哪些?这4款千万不要错过

视频压缩的方法有很多种&#xff0c;像我们手机里的视频剪辑工具&#xff0c;手机和电脑自带的压缩功能&#xff0c;在线压缩网站&#xff0c;专业压缩软件压缩等等。不同的场景和需求下大家可以选择不同的工具&#xff0c;但是如果碰到需要大量和经常压缩视频的话&#xff0c;…...

【Python爬虫系列】_016.关于登录和验证码

我 的 个 人 主 页&#xff1a;&#x1f449;&#x1f449; 失心疯的个人主页 &#x1f448;&#x1f448; 入 门 教 程 推 荐 &#xff1a;&#x1f449;&#x1f449; Python零基础入门教程合集 &#x1f448;&#x1f448; 虚 拟 环 境 搭 建 &#xff1a;&#x1f449;&…...

基于opencv实现双目立体匹配点云距离

双目相机或两个单目相机。 一、相机标定 MATLAB软件&#xff0c;打开双目标定app。 点击add images&#xff0c;弹出加载图像的窗口&#xff0c;分别导入左图和右图&#xff0c;设置黑白格长度&#xff08;标定板的长度一般为20&#xff09;。 点击确定&#xff0c;弹出加载…...

RabbitMQ高级篇,进阶内容

强烈建议在看本篇博客之前快速浏览文章&#xff1a;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; }…...

项目进度

变为负进度了&#xff0c;还是要用baseservlet&#xff0c;我就又重新写了一部分&#xff0c;看了好几遍视频&#xff0c;突然就想明白了&#xff0c;感觉每次要上课&#xff0c;就时间不连续思路总是断&#xff0c;今天晚自习算是搞懂了怎么写了&#xff0c;就是代码有点多&am…...

Android的内核

Android的内核是基于Linux的长期支持版本的“Android通用内核(ACK)”。 Android作为一个广泛使用的操作系统&#xff0c;其根基在于内核的设计和功能。下面将深入探讨Android内核的各个方面&#xff0c;从其基本结构到与Linux内核的关系&#xff0c;再到内核的版本管理及在设备…...

Github Wiki 超链接 转 码云Gitee Wiki 超链接

Github Wiki 超链接 转 码云Gitee Wiki 超链接 Github 是 &#xff1a;[[相对路径]] Gitee 是 &#xff1a;[链接文字](./相对路径) 查找&#xff1a;\[\[(.*?)\]\] 替换&#xff1a;[$1]\(./$1\) 或替换&#xff1a;**[$1]\(./$1\)** &#xff08;码云的超链接&#xff0c;很…...

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文件&#xff0c;应该是下载时出现问题&#xff0c;重复下载无法解决问题&#xff0c;只能重新安装brew。 步骤1&#xff08;安装 brew&#xff09;&#xff1a; /bin/zsh -c “$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/ra…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...