# 517. 礼盒的最大甜蜜度 (Medium)

## 问题描述
[2517. 礼盒的最大甜蜜度 (Medium)](https://leetcode.cn/problems/maximum-tastiness-of-candy-basket/)
给你一个正整数数组 `price` ，其中 `price[i]` 表示第 `i` 类糖
果的价格，另给你一个正整数 `k` 。

商店组合 `k` 类 **不同** 糖果打包成礼盒出售。礼盒的 **甜蜜度
** 是礼盒中任意两种糖果 **价格** 绝对差的最小值。

返回礼盒的 **最大** 甜蜜度。

**示例 1：**

```
输入：price = [13,5,1,8,21,2], k = 3
输出：8
解释：选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8
, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。

```

**示例 2：**

```
输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。

```

**示例 3：**

```
输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

```

**提示：**

- `1 <= price.length <= 10⁵`
- `1 <= price[i] <= 10⁹`
- `2 <= k <= price.length`

## 解题思路
对于这种**最小化最大值**或者**最大化最小值**的题目，应该想到**二分答案**。

由于本题可以任意组合糖果，与糖果之间的顺序无关，因此可以考虑先对 `price` 数组排序。

记本题的正确答案为 `ans`，如果 $mid \leq ans$，那么糖果可以被打包成 $k$ 类糖果礼盒，否则不可以打包成 $k$ 类礼盒，于是我们就找到了满足二分的二段性条件。

同时，我们仍需要使用**二分查找**来判断是否可以打包成 $k$ 类糖果礼盒，基于排序后的 `price` 数组。

## 代码
```cpp
class Solution {
  public:
    int Bsearch(int target, vector<int> &price, int left) {
        int right = price.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (price[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    bool Check(int mid, vector<int> &price, int k, int n) {
        int start = 0;
        for (int i = 0; i < k - 1; ++i) {
            start = Bsearch(price[start] + mid, price, start);
            // cout << start << " start\n";
            if (start >= n) {
                return false;
            }
        }
        return true;
    }
    int maximumTastiness(vector<int> &price, int k) {
        // 先排序，然后考虑是二分答案还是双指针
        sort(price.begin(), price.end());
        // 二分答案，时间复杂度为 log(price[i]) * k * log(n)
        int n = price.size();
        int left = 0, right = (price[n - 1] - price[0]) / (k - 1) + 1; // 先看看 k 行不行，不行就改成 2
        while (left < right) {
            // 左闭右开
            int mid = left + (right - left) / 2;
            if (Check(mid, price, k, n)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1;
    }
};
```