2517.礼盒的最大甜蜜度

链接：2517.礼盒的最大甜蜜度
难度：Medium
标签：贪心、数组、二分查找、排序
简介：返回礼盒的 最大 甜蜜度。

题解 1 - cpp

• 编辑时间：2022-12-25
• 执行用时：172ms
• 内存消耗：49.4MB
• 编程语言：cpp
• 解法介绍：二分答案。

class Solution {
public:
    int n, k;
    vector<int> price;
    int maximumTastiness(vector<int>& price, int k) {
        sort(price.begin(), price.end());
        n = price.size();
        this->k = k;
        this->price = price;
        int l = 0, r = price[n - 1] - price[0], m;
        while (l < r) {
            m = (l + r + 1) / 2;
            if (check(m)) l = m;
            else r = m - 1;
        }
        return l;
    }
    bool check(int num) {
        int cnt = 1, cur = price[0];
        for (int i = 1; i < n; i++) {
            if (cur + num <= price[i]) {
                cnt++;
                cur = price[i];
            }
        }
        return cnt >= k;
    }
};

题解 2 - cpp

• 编辑时间：2023-06-01
• 执行用时：212ms
• 内存消耗：47.3MB
• 编程语言：cpp
• 解法介绍：二分答案，尽可能找差超过target的数量。

class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        sort(price.begin(), price.end());
        int n = price.size(), l = 0, r = price[n - 1] - price[0];
        while (l < r) {
            int m = (l + r + 1) / 2, cnt = 1, prev = price[0];
            for (int i = 1; i < n; i++) {
                if (price[i] - prev >= m) cnt++, prev = price[i];
            }
            if (cnt < k) r = m - 1;
            else l = m;
        }
        return l;
    }
};

题解 3 - python

• 编辑时间：2023-06-01
• 执行用时：996ms
• 内存消耗：27.5MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()
        n = len(price)
        l = 0
        r = price[n-1]-price[0]
        while l < r:
            m = (l+r+1)//2
            cnt = 1
            prev = price[0]
            for i in range(1, n):
                if price[i] - prev >= m:
                    cnt += 1
                    prev = price[i]
            if cnt < k:
                r = m-1
            else:
                l = m
        return l

题解 4 - rust

• 编辑时间：2023-06-01
• 执行用时：44ms
• 内存消耗：3.9MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
pub fn maximum_tastiness(mut price: Vec<i32>, k: i32) -> i32 {
    price.sort();
    let n = price.len();
    let mut l = 0;
    let mut r = price[n - 1] - price[0];
    while l < r {
        let m = (l + r + 1) / 2;
        let mut cnt = 1;
        let mut prev = price[0];
        for i in 1..n {
            if price[i] - prev >= m {
                cnt += 1;
                prev = price[i];
            }
        }
        if cnt < k {
            r = m - 1;
        } else {
            l = m
        }
    }
    l
}
}