礼盒的最大甜蜜度

记牢:甜蜜度 x 越小越容易凑够 k 个,可行性单调,于是在 0 到 max 减 min 上二分 x。检验一个 x:排序后贪心,差不小于 x 就选,选够 k 颗即可达,可达就把左界收到 mid、否则右界降到 mid 减 1。二分的是甜蜜度值,不是下标。

总览 · 原始价格还没排序：先看清画面。上面这排是原始价格 8,1,5,3,顺序是乱的。我们要从这 4 类里挑 3 类,让盒中两两价差里最小的那个尽量大。右边面板记三件事:甜蜜度的候选范围、当前正在检验的甜蜜度 x、已经选中的糖果数,现在都还没开始。思路不是硬挑,而是二分猜一个甜蜜度 x,再验证它凑不凑得够 3 颗。

排序 · 从小到大排好：第一步先排序,把 8,1,5,3 排成从小到大的 1,3,5,8。为什么必须排序,因为等会儿的贪心是从最小的价格出发、一路往大走,只有有序才能保证「每次尽量早选、给后面留空间」这套贪心成立。排好之后,数轴上这四颗糖果就均匀铺开了,后面所有操作都在这排有序价格上做。

定范围 · 在 0 到 7 上二分甜蜜度：框定答案范围。甜蜜度最小能到 0,比如有两颗价格一样时最小差就是 0;最大不会超过最贵和最便宜之差,也就是 8 减 1 等于 7。所以答案一定落在 0 到 7 这个闭区间里。接下来不逐个试,而是二分:取中点当候选甜蜜度 x,验证「能不能选出 3 颗,让它们两两差都不小于 x」。请记住,右边面板里动的是甜蜜度 x 的范围,数组这排糖果始终不动。

第一轮 · 取中点 x = 4：开始第一轮二分。当前范围 0 到 7,取中点,x 等于 0 加 7 加 1 再整除 2 得 4。注意这里取中点特意加了个 1、往上取整,这是「可达就把左界收到 mid」那一支必须的防死循环写法。这一轮就问:能不能选出 3 颗糖果,让它们两两差都不小于 4?下面从最小的糖果开始逐颗贪心地挑。

第一轮 · 看价格 1 · 选：贪心从最小的 1 开始。这里有个巧劲:把上一次选中的价格 pre 初始设成负的 x,也就是 -4,这样 1 减去 -4 等于 5,一定不小于 4,所以最小的这颗必被选中。选它,已选记 1 颗,把 pre 更新成 1。道理是:最便宜的糖果留着没意义,越早选、越能给后面腾出价格空间。

第一轮 · 看价格 3 · 跳：看价格 3,它减去上一次选中的 1 等于 2。这个差小于门槛 4,离上一颗太近,选了会拉低最小差,跳过它,继续看下一颗。

第一轮 · 看价格 5 · 选：看价格 5,它减去上一次选中的 1 等于 4。这个差不小于门槛 4,说明它离上一颗够远,选进礼盒,已选变成 2 颗,pre 更新成 5。

第一轮 · 看价格 8 · 跳：看价格 8,它减去上一次选中的 5 等于 3。这个差小于门槛 4,离上一颗太近,选了会拉低最小差,跳过它,继续看下一颗。

第一轮 · x = 4 不可达：一趟贪心扫完,只选到 2 颗,不够 3 颗,说明甜蜜度定到 4 太苛刻,糖果被门槛卡得太狠、凑不齐。那 4 以及更大的都不行,把右界降到 3,范围变成 0 到 3,往更小里找。

第二轮 · 取中点 x = 2：第二轮二分。上一轮把范围收到了 [0, 3],取中点得到候选甜蜜度 x 等于 2。同样问一句:能不能选出 3 颗,让两两差都不小于 2?贪心从最小的糖果往上挑。

第二轮 · 看价格 1 · 选：贪心从最小的 1 开始。这里有个巧劲:把上一次选中的价格 pre 初始设成负的 x,也就是 -2,这样 1 减去 -2 等于 3,一定不小于 2,所以最小的这颗必被选中。选它,已选记 1 颗,把 pre 更新成 1。

第二轮 · 看价格 3 · 选：看价格 3,它减去上一次选中的 1 等于 2。这个差不小于门槛 2,说明它离上一颗够远,选进礼盒,已选变成 2 颗,pre 更新成 3。

第二轮 · 看价格 5 · 选：看价格 5,它减去上一次选中的 3 等于 2。这个差不小于门槛 2,说明它离上一颗够远,选进礼盒,已选变成 3 颗,pre 更新成 5。

第二轮 · 看价格 8 · 选：看价格 8,它减去上一次选中的 5 等于 3。这个差不小于门槛 2,说明它离上一颗够远,选进礼盒,已选变成 4 颗,pre 更新成 8。

第二轮 · x = 2 可达：一趟贪心扫完,选够了 4 颗,不小于要求的 3 颗,说明甜蜜度做到 2 是办得到的。既然 2 能到,那更大的甜蜜度值得一试,把左界收到 2,范围变成 2 到 3。注意 2 本身可能就是答案,所以左界取 2 而不是 2 加 1,继续往更大里试。

第三轮 · 取中点 x = 3：第三轮二分。上一轮把范围收到了 [2, 3],取中点得到候选甜蜜度 x 等于 3。同样问一句:能不能选出 3 颗,让两两差都不小于 3?贪心从最小的糖果往上挑。

第三轮 · 看价格 1 · 选：贪心从最小的 1 开始。这里有个巧劲:把上一次选中的价格 pre 初始设成负的 x,也就是 -3,这样 1 减去 -3 等于 4,一定不小于 3,所以最小的这颗必被选中。选它,已选记 1 颗,把 pre 更新成 1。

第三轮 · 看价格 3 · 跳：看价格 3,它减去上一次选中的 1 等于 2。这个差小于门槛 3,离上一颗太近,选了会拉低最小差,跳过它,继续看下一颗。

第三轮 · 看价格 5 · 选：看价格 5,它减去上一次选中的 1 等于 4。这个差不小于门槛 3,说明它离上一颗够远,选进礼盒,已选变成 2 颗,pre 更新成 5。

第三轮 · 看价格 8 · 选：看价格 8,它减去上一次选中的 5 等于 3。这个差不小于门槛 3,说明它离上一颗够远,选进礼盒,已选变成 3 颗,pre 更新成 8。

第三轮 · x = 3 可达：一趟贪心扫完,选够了 3 颗,不小于要求的 3 颗,说明甜蜜度做到 3 是办得到的。把左界收到 3,范围变成 3 到 3。左右界撞到一块儿了,二分到这一步就该收束了。

收束 · 左右界重合于 3：二分收束了。左界和右界都停在 3,说明 3 是能达到的最大甜蜜度:它可达,而比它大的 4 已经验证过办不到。回看这颗最优选择,贪心选出的正是价格 1、5、8 这三类,它们两两差里最小的正好是 3。

完成 · 最大甜蜜度 = 3：收个尾。这道题的巧劲在于把「怎么选 k 类糖果」这个难题,翻译成「甜蜜度能不能达到 x」这个好答的判断题,再靠单调性二分甜蜜度。price 排序成 1,3,5,8、k = 3,我们只检验了 4、2、3 这 3 个候选,就锁定最大甜蜜度是 3。二分把候选个数从线性压成对数级,每次贪心检查线性扫一遍糖果,又快又稳。

边界:全相等时甜蜜度只能是 0;有重复价格排序后照选,最大差就是答案;题面例子 1,2,5,8,13,21 选 3 颗,最大甜蜜度 8。都能用「排序加贪心」的可行性检查验证。

面试重点:甜蜜度门槛越低越容易选够 k 颗,可行性单调所以能二分;检验用排序加贪心、能选就选,靠交换论证最优;求最大可达值要用 (lo+hi+1) 右移配 lo = mid,防止死循环。