本文主要是介绍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.length1 <= 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;}
};这篇关于LeedCode 1402. 做菜顺序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
