最大最小值,或者最小最大值,可以考虑二分。
这道题的甜蜜度就存在单调性,所以可以直接二分甜蜜度。
剩下最后一个问题,就是如何写check函数?可以先对Price数组进行排序,排完序后,与price[i]
距离越远的price
,其与price[i]
的绝对差就越大。
因此我们可以贪心的检测,二分出mid
后,选取price[0]
作为第一个糖果,然后从前往后遍历,如果当前糖果的price
和上一个糖果的price
的绝对差\(\geq mid\),那么我们就选取这个糖果进来,令cnt++
。最后检测是否有\(cnt \geq k\)即可。
为什么要选取price[0]
作为第一个糖果呢?因为price[0]
是甜蜜度最小的糖果,选取任何其他的糖果作为第一个,产生的集合都不可能比它大,最多相等。