Day72 | 灵神 | 二分查找 礼盒的最大甜蜜度

#Day72 | 灵神 | 二分查找 礼盒的最大甜蜜度

2517.礼盒的最大甜蜜度

2517. 礼盒的最大甜蜜度 - 力扣（LeetCode）

昨天说：灵神说看到最小化最大值就肯定是二分查找，这点要记住

今天就碰到了最大化最小值，这个也是二分

思路：

还是老套路，先看二分的是什么，这道题求的是甜蜜度，那么二分的是甜蜜度，而不是原数组

那么二分区间即甜蜜度的区间是多少呢？最大值肯定就是max(price)-min(price)=r了，最小值那肯定就是0了，即数组数字都一样，区间就是[0,r]，笔者用的左闭右开，那就是[0,r+1)

然后套路模板就可以写了

接下来就是找判断条件，即写出check函数了

我觉得这个是最难的

说实话我这个不太会写，看了灵神的，可以理解灵神的写法，但是自己想一点都想不出来，可能还是刷的少了

2517. 礼盒的最大甜蜜度 - 力扣（LeetCode）

灵神代码：

灵神用的左开右开区间

class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        auto f = [&](int d) -> int {
            int cnt = 1, pre = price[0]; // 先选一个最小的甜蜜度
            for (int p : price) {
                if (p >= pre + d) { // 可以选
                    cnt++;
                    pre = p; // 上一个选的甜蜜度
                }
            }
            return cnt;
        };

        ranges::sort(price);
        int left = 0;
        int right = (price.back() - price[0]) / (k - 1) + 1;
        while (left + 1 < right) { // 开区间不为空
            // 循环不变量：
            // f(left) >= k
            // f(right) < k
            int mid = left + (right - left) / 2;
            (f(mid) >= k ? left : right) = mid;
        }
        return left; // 最大的满足 f(left) >= k 的数
    }
};