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