【算法】Maximum Tastiness of Candy Basket 礼盒的最大甜蜜度-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】Maximum Tastiness of Candy Basket 礼盒的最大甜蜜度。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Maximum Tastiness of Candy Basket 礼盒的最大甜蜜度

问题描述：

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类不同糖果打包成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖果价格绝对差的最小值。

返回礼盒的最大甜蜜度。

price.length 范围 $1,10^5]$ , price[i] 范围 $1,10^9]$ ,k 范围[2,price.length]

分析

一个礼盒的甜蜜度是由价格差最小的决定的。如果单独考虑一个礼盒计算其甜蜜度tastiness，这个结果一定是在2个相邻的candy之间产生。

如果暴力的处理，就需要暴力去枚举所有可能，这个思路的时间复杂度太高，很明显走不通。

随便选 $k$ 类 $c an d y$ ，打包成为一个礼盒，它的甜蜜度为X，这个x是可以计算，但是目标是要使X最大。

一种方式就暴力，穷举出所有的甜蜜度，找到最大的。
另一种方式就是假设一个甜蜜度X，判断是否存在一个这样的礼盒。

很明显后一种在规模较大的情况下更加合理。

问题就变成是否可以快速找到 $k 类 c an d y ，它的甜蜜度 x >= t a r g e t$ .

如果可以找到这个组合，说明 $t a r g e t 应该 >= x, 否则 t a r g e t < x - 1.$ 很明显是一个二分思路。
然后需要解决的就是一个check方法，之前已经说过，影响一个礼盒的甜蜜度，一定是2个相邻的 $c an d y$ ，所以需要将 $p r i ce$ 从小到大排序。
然后再长度 $N$ 的元素中，找出 $k$ 个元素，而且相邻之间的差值 $d i ff >= t a r g e t$ 。

check的实现方式有很多，可以递归回溯，可以dp，思路就是尽可能的选择更多的元素.

当已经选择的组合中最后的元素为 $a [i - 1]$ ,那么当前元素是否入选，就取决于 $c u r - a [i - 1] >= t a r g e t$ ,满足则入选，否则就跳过，基于这个贪心的思路，可以选择出最多的元素组合。

代码

public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int n = price.length;
        int l = 0,r = price[n-1]-price[0],mid=0;
        while(l<r){
            mid = l + (r-l+1)/2; 
            if(check(price,mid)<k){
                r = mid-1;                
            }
            else{
                l = mid;
            }
        }
        return l; 
    }
    public int check(int[] arr ,int diff){
        int n = arr.length,cnt = 1,pre = arr[0];
        for(int i =1;i<n;i++){
            if(arr[i]-pre>=diff){
                cnt++;
                pre = arr[i];
            }
        }
        return cnt;
    }