【LeetCode】 1402. Reducing Dishes

Description

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.

Constraints:
n == satisfaction.length
1 <= n <= 500
-1000 <= satisfaction[i] <= 1000

一個廚師收集了他 n 盤菜餚的 satisfaction (滿意度)等級數據。廚師可以在一個單位時間內完成一道任意的菜餚。
一道菜餚的喜歡時間係數定義為烹煮這道菜餚（包含之前所有菜餚）花費的時間乘上菜餚的滿意度。也就是 time[i] * satisfaction[i] (時間[i] * 滿意度[i])。
回傳廚師準備菜肴後可獲得的最大喜歡時間係數之和。
菜餚可以按照任意順序做準備，廚師也可以捨棄任意數量的菜餚以獲得最大值。

限制：
n == satisfaction.length
1 <= n <= 500
-1000 <= satisfaction[i] <= 1000

Example:

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.

Solution

• 題目有些拗口實際上就是
  • 給一陣列，可隨意改變順序，甚至可隨意丟棄元素
  • 改變完陣列後，第一個元素乘一加上第二的元素乘二…求總和最大為多少
• 第一個直覺的想法是只留下非負數，但其實這是錯的，因為將小的負數放在前面可以使後面的正數加更多，因此要策略性地留下負數
  • 例如第一個範例測資
• 一個關鍵的想法是最後答案的陣列一定會按照大小排序，因此我們可以將陣列先排序，然後思考要拿多少負數
• 我們每加一個負數到陣列時，喜歡時間係數(答案)會如何改變？
  • 加上目前陣列的總和和加入的負數
• 因此要將答案最大化，就是目前陣列總和大於零就可以繼續拿負數，反之則停止

---

• 感謝實驗室的小夥伴們與我一起完成這題

Code

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        int sum = 0;
        int ans = 0;
        sort(satisfaction.rbegin(), satisfaction.rend());

        for(int i = 0; i < satisfaction.size(); i++)
        {
            sum += satisfaction[i];
            if(sum < 0)
                break;
            ans += sum;
        }
        return ans;
    }
};

tags: LeetCode C++