给你一个正整数数组 price ,其中 price[i] 表示第 i 类糖果的价格,另给你一个正整数 k 。 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。 返回礼盒的 最大 甜蜜度
时间: 2024-02-29 18:55:19 浏览: 93
这是一个经典的二分答案问题。首先可以想到甜蜜度的上限为 max(price)-min(price),因为任意两个数的差值不可能超过这个范围。
然后我们可以考虑二分答案,假设当前二分到的甜蜜度为 mid,那么我们需要判断能否用 k 个礼盒将所有糖果都包装起来,使得每个礼盒内任意两个糖果的价格差不超过 mid。
这个问题可以使用贪心算法来解决。我们首先将价格数组按照从小到大排序,然后从前往后遍历。对于当前遍历到的糖果,我们尝试将其放入前面已经放置好的礼盒中,如果能够放入一个礼盒中使得这个礼盒内任意两个糖果的价格差不超过 mid,那么就将其放入该礼盒中。否则,我们就新开一个礼盒,并将当前糖果放入其中。
如果最终使用的礼盒数量不超过 k,那么说明当前的 mid 是可行的,我们可以继续尝试使用更大的 mid。否则,说明当前的 mid 不可行,我们需要尝试使用更小的 mid。
时间复杂度为 O(nlogn * log(max(price)-min(price)))。
阅读全文