2517.?禮盒的最大甜蜜度

給你一個正整數(shù)數(shù)組?price，其中?price[i]表示第?i類糖果的價格，另給你一個正整數(shù)?k。

商店組合?k類?不同糖果打包成禮盒出售。禮盒的?甜蜜度是禮盒中任意兩種糖果?價格絕對差的最小值。

【資料圖】

返回禮盒的?最大?甜蜜度。

先來個錯誤示范：

我的思路第一步就錯了，我直接當(dāng)成子序列問題，但其實沒必要。比如一個禮盒：

[5,3,2,4,9]

求禮盒的甜蜜度，不需要把所有的元素兩兩組合，只需要先排序，變成：

[2,3,4,5,9]

那么對于2這個元素，與3組合就是2的所有組合中的最小值，后面所有的組合值都更大，可以直接無視。

為什么可以這樣？因為所有元素都是正整數(shù)，換言之具有單調(diào)性。

這里反映出我的思考方式還是太容易鉆死胡同，也沒有用分治法，先思考怎么求禮盒的甜蜜度，再求最終問題的答案，而是直接一股腦莽了進(jìn)去。

我最終得到的思路是這樣的:

我可以從price中減去元素，最終得到我要的那個包含最大甜蜜度的禮盒。

給price排序，從price里面減去甜蜜度最小的組合的其中一個元素，讓甜蜜度變大。我能保證每一次操作都是最優(yōu)的，同時最終我要的那個禮盒一定可以通過這樣的減操作得到，所以我可以用這種方法得到答案。

實際上根本不行。因為這個減操作的順序會影響最終的結(jié)果，我不知道最終的禮盒是用什么順序執(zhí)行減操作得到的，換言之局部最優(yōu)解不一定是全局最優(yōu)解，我得枚舉全部的順序。

分析完錯誤原因，來看正確答案：二分查找。

然后我在想：二分的本質(zhì)就是一個值跟一組區(qū)間的關(guān)系吧，隨著這個值的增大或減小，區(qū)間的數(shù)量跟大小也會增加或減少。

一個題目，只要能找到這樣的關(guān)系，就可以用二分。

待續(xù)：