LeedCode 1402. 做菜顺序

一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间。

一道菜的 「 like-time 系数 」定义为烹饪这道菜结束的时间（包含之前每道菜所花费的时间）乘以这道菜的满意程度，也就是 time[i]*satisfaction[i] 。

返回厨师在准备了一定数量的菜肴后可以获得的最大 like-time 系数 总和。

你可以按 任意 顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。

示例 1：

输入：satisfaction = [-1,-8,0,5,-9]
输出：14
解释：去掉第二道和最后一道菜，最大的 like-time 系数和为 (-1*1 + 0*2 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。

示例 2：

输入：satisfaction = [4,3,2]
输出：20
解释：可以按照任意顺序做菜 (2*1 + 3*2 + 4*3 = 20)

示例 3：

输入：satisfaction = [-1,-4,-5]
输出：0
解释：大家都不喜欢这些菜，所以不做任何菜就可以获得最大的 like-time 系数。

提示：

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

 思路

1. 首先，获取满意度数组的大小 `n`，以及初始化两个变量 `num` 和 `num1`，分别代表当前的满意度总和和满意度的累计贡献。初始时，`num` 和 `num1` 均为0。

2. 对满意度数组 `satisfaction` 进行降序排序，以便后续从高到低选择满意度。

3. 使用循环遍历排序后的满意度数组 `satisfaction`，对每个满意度进行处理。

   - 将当前满意度加到满意度总和 `num` 上。
   - 如果当前满意度总和 `num` 小于等于0，说明后面的满意度不可能使总满意度更大，因此跳出循环。
   - 否则，将当前满意度总和 `num` 加到满意度的累计贡献 `num1` 上。

4. 最后返回满意度的累计贡献 `num1` 作为最大满意度值。

使用贪心策略，每次选择当前满意度后，根据当前的满意度总和判断是否继续选择后面的满意度，以获得最大的满意度总和。

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        int n = satisfaction.size();
        int num = 0, num1 = 0;
        sort(satisfaction.rbegin(), satisfaction.rend()); // 按照满意程度降序排序
        for (int i = 0; i < n; i++) {
            num += satisfaction[i];
            if (num <= 0) { // 如果加入当前菜后总和小于等于0，则不再考虑后面的菜
                break;
            }
            num1 += num; // 累加当前的 like-time 系数之和
        }
        return num1;
    }
};