1402.Reducing Dishes

tags: `Hard`,`Array`,`DP`,`Greedy`,`Sorting`

題目描述

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.

Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i].

Return the maximum sum of like-time coefficient that the chef can obtain after dishes preparation.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

範例

Example 1:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

Example 2:

Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

Example 3:

Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People do not like the dishes. No dish is prepared.

Constraints:

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

解答

Python

作法: Greedy，先對菜餚做排序，價值越高的菜餚要累加越多次，直到當前滿意度 < 0 時，則停止計算











class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction = sorted(satisfaction)
        suffix_sum, max_satisfaction = 0, 0
        
        for i in range(len(satisfaction) - 1, -1, -1):
            if suffix_sum + satisfaction[i] > 0:
                suffix_sum += satisfaction[i]
                max_satisfaction += suffix_sum

        return max_satisfaction

Ron ChenWed, Mar 29, 2023









class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        total, ans = 0, 0
        for value in satisfaction:
            if total + value <= 0: break
            total += value
            ans += total
        return ans

Yen-Chi ChenWed, Mar 29, 2023














class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        if satisfaction[0] <= 0:
            return 0

        total = 0
        max_value = 0
        for i, _ in enumerate(satisfaction):
            total = sum([(i-j+1)*satisfaction[j] for j in range(i+1)])
            if total > max_value:
                max_value = total

        return max_value

gpwork4uThur, Mar 30, 2023

C++













class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end(), greater<int>());
        int sum = 0, ans = 0;
        for (auto value : satisfaction) {
            sum += value;
            if (sum <= 0) break;
            ans += sum;
        }
        return ans;
    }
};

Yen-Chi ChenWed, Mar 29, 2023

Javascript















function maxSatisfaction(satisfaction) {
  satisfaction.sort((a, b) => b - a);
  let max = 0;
  let sum = 0;
  for (const num of satisfaction) {
    sum += num;
    if (sum > 0) {
      max += sum;
    } else {
      break;
    }
  }

  return max;
}

MarsgoatWed, Mar 29, 2023

Reference

回到題目列表