2023.6.1 礼盒的最大甜蜜度

发布时间 2023-06-01 13:57:56作者: 烤肉kr

image

最大最小值,或者最小最大值,可以考虑二分。
这道题的甜蜜度就存在单调性,所以可以直接二分甜蜜度。

剩下最后一个问题,就是如何写check函数?可以先对Price数组进行排序,排完序后,与price[i]距离越远的price,其与price[i]的绝对差就越大。

因此我们可以贪心的检测,二分出mid后,选取price[0]作为第一个糖果,然后从前往后遍历,如果当前糖果的price和上一个糖果的price的绝对差\(\geq mid\),那么我们就选取这个糖果进来,令cnt++。最后检测是否有\(cnt \geq k\)即可。

为什么要选取price[0]作为第一个糖果呢?因为price[0]是甜蜜度最小的糖果,选取任何其他的糖果作为第一个,产生的集合都不可能比它大,最多相等。