网站内容建设ppt模板,校园资源共享网站建设,文库网站开发教程,做网站买二手域名2023-03-29每日一题
一、题目编号
二、题目链接
点击跳转到题目位置
三、题目描述
给你一个正整数数组 price #xff0c;其中 price[i] 表示第 i 类糖果的价格#xff0c;另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两…2023-03-29每日一题
一、题目编号
二、题目链接
点击跳转到题目位置
三、题目描述
给你一个正整数数组 price 其中 price[i] 表示第 i 类糖果的价格另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。
提示
1 price.length 1051 price[i] 1092 k price.length
四、解题代码
class Solution {bool judge(int degree, vectorint price , int k, int n){int num 1;int index price[0];for(int i 1; i n; i){if(price[i] - index degree){index price[i];num;}}if(num k){return true;}return false;}public:int maximumTastiness(vectorint price, int k) {sort(price.begin(), price.end());int n price.size();int left 0;int right price[n - 1] - price[0];int ans -1;while(left right){int mid ((right - left) 1) left;if(judge(mid, price, k, n) true){ans mid;left mid1;} else{right mid-1;}}return ans;}
};五、解题思路
(1) 这道题目采用的是二分答案贪心的方式来解决本道题目。
(2) 首先将价格从低到高来进行排序那么最小的甜蜜度肯定为0最大的甜蜜度肯定为price[n-1] - price[0]。那么我们就可以用二分答案的方式在这个甜蜜度区间内进行查找直到查找到答案。
(3) 那么我们怎么判断二分查找的答案是正确的呢。假设我们判断甜蜜度degree的答案是正确那就是遍历一个有序数组找到k个满足间隔大于等于degree的数。这个问题显然是熟悉的贪心思路样板为活动安排问题。
(4) 最后返回二分搜索出来的答案即可。
