1402.做菜顺序

链接：1402.做菜顺序
难度：Hard
标签：贪心、数组、动态规划、排序
简介：返回厨师在准备了一定数量的菜肴后可以获得的最大 like-time 系数 总和。

题解 1 - rust

• 编辑时间：2023-10-22
• 内存消耗：1.98MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn max_satisfaction(mut satisfaction: Vec<i32>) -> i32 {
        satisfaction.sort();
        let n = satisfaction.len();
        let mut res = 0;
        let mut nsum = 0;
        let mut vsum = 0;
        for i in 0..n {
            nsum += (i as i32 + 1) * satisfaction[i];
            vsum += satisfaction[i]
        }
        res = res.max(nsum);
        for i in 1..n {
            if satisfaction[i] >= 0 {
                break;
            }
            nsum -= vsum;
            vsum -= satisfaction[i - 1];
            res = res.max(nsum);
        }
        res
    }
}

题解 2 - python

• 编辑时间：2023-10-22
• 执行用时：24ms
• 内存消耗：15.69MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        n = len(satisfaction)
        res = nsum = sum((i + 1) * satisfaction[i] for i in range(n))
        sumv = sum(satisfaction)
        for i in range(1, n):
            if satisfaction[i] >= 0: break
            nsum -= sumv
            sumv -= satisfaction[i - 1]
            res = max(res, nsum)
        return max(0, res)

题解 3 - cpp

• 编辑时间：2023-10-22
• 执行用时：4ms
• 内存消耗：7.93MB
• 编程语言：cpp
• 解法介绍：排序后贪心判断。

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        int n = satisfaction.size(), nsum = 0, vsum = 0, res = 0;
        for (int i = 0; i < n; i++) {
            nsum += (i + 1) * satisfaction[i];
            vsum += satisfaction[i];
        }
        res = max(res, nsum);
        for (int i = 1; i < n; i++) {
            if (satisfaction[i] >= 0) break;
            nsum -= vsum;
            vsum -= satisfaction[i - 1];
            res = max(res, nsum);
        }
        return res;
    }
};