---
# System prepended metadata

title: 2517. Maximum Tastiness of Candy Basket
tags: [Leetcode, Binary Search, Medium]

---

# 2517. Maximum Tastiness of Candy Basket
###### tags: `Leetcode` `Medium` `Binary Search`
Link: https://leetcode.com/problems/maximum-tastiness-of-candy-basket/description/
## 思路
binary search by value
注意```end```的初始值```price[n-1]-price[0]+1``` 因为我们要找最大值 所以需要找到最小的不满足条件的值 减1就是答案 由于```price[n-1]-price[0]```可能是答案 所以end的初始值需要+1
## Code
java
```java=
class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int n = price.length;
        int start = 0, end = price[n-1]-price[0]+1;
        while(start<end){
            int mid = start+(end-start)/2;
            if(check(price, mid, k)){
                start = mid+1;
            }
            else end = mid;
        }
        return start-1;
    }
    public boolean check(int[] price, int diff, int k){
        int last = price[0];
        int count = 1;
        for(int i=1; i<price.length; i++){
            if(last+diff<=price[i]){
                count++;
                last = price[i];
            }
            if(count>=k) return true;
        }
        return false;
    }
}
```
python
```python=
class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()
        n = len(price)

        def check(price: List[int], diff:int, k:int) -> bool:
            last = price[0]
            count = 1
            for i in range(1, len(price)):
                if last+diff<=price[i]:
                    count += 1
                    last = price[i]
                if count==k: return True
            return False
        
        start = 0
        end = price[n-1]-price[0]+1
        while start<end:
            mid = start+(end-start)//2
            if check(price, mid, k):
                start = mid+1
            else: end = mid
        return start-1
```