Leetcode 2517. Maximum Tastiness of Candy Basket

[Woodyiiiiiii]

2517. Maximum Tastiness of Candy Basket

相关题目

• 475. Heaters
• 2226. Maximum Candies Allocated to K Children
• 875. Koko Eating Bananas
• 1802. Maximum Value at a Given Index in a Bounded Array (O(nlgn)还TLE了，二分后作等差数列求和，O(lgn)时间复杂度)
• 2439. Minimize Maximum of Array (有点小绕，抓住lo/hi移动，注意别搞成单调栈了)
• 754. Reach a Number (难点在于能否想到二分+判断函数)
• 2616. Minimize the Maximum Difference of Pairs (二分+贪心)
• 1898. Maximum Number of Removable Characters

这道题一开始完全想不到二分，不知道怎么应用二分。

这时候要用反向思维，把答案作为二分的轴。

先要排序，排除掉数组元素位置的影响。因为目的是找到之前差值大于等于这个轴的元素。

同时注意l包含，r不包含，所有r左移是r=mid；返回值直接是l-1。

class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);

        int l = 0, r = 1000000000;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(price, k, mid)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        
        return l - 1;
    }

    boolean check(int[] price, int k, int mid) {
        int cnt = 1;
        int last = price[0];
        int kk = 1;
        while (kk < price.length && cnt < k) {
            if (price[kk] - last >= mid) {
                ++cnt;
                last = price[kk];
            }
            ++kk;
        }
        return cnt == k;
    }

}

tips:

1. 发现，对于结果是l-1还是l，根据check函数分支来判断，如果是l = mid + 1则是l-1，否则r=mid则是l
2. 一般二分的使用场景是有题目条件变量范围特别大，比如到1e9
3. check函数大部分可能用到数学知识，或者剪枝，还有贪心，用来尽可能缩减时间

---

• https://leetcode.com/problems/maximum-tastiness-of-candy-basket/description/
• https://leetcode.com/problems/maximum-tastiness-of-candy-basket/solutions/2947983/c-java-python-binary-search-and-sorting/