做菜顺序【LC1402】
一个厨师收集了他
n道菜的满意程度satisfaction，这个厨师做出每道菜的时间都是 1 单位时间。一道菜的 「 like-time 系数 」定义为烹饪这道菜结束的时间（包含之前每道菜所花费的时间）乘以这道菜的满意程度，也就是
time[i]*satisfaction[i]。返回厨师在准备了一定数量的菜肴后可以获得的最大 like-time 系数 总和。
你可以按 任意 顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。
思路
- 贪心：
- 为了获得最大的 like-time 系数 总和，应按照满意度升序做菜；
- 满意度大的最后再做；
- 满意度为负数的菜，可以选择做或者不做。
- 排序后倒序遍历，增加一道菜like-time系数变化量为：satisfaction[i] +…+ satisfaction[n-1]，如果大于0，那么可以使 like-time 系数 总和增加，那么选择做这道菜
- 实现
class Solution { public int maxSatisfaction(int[] satisfaction) { // 贪心：为了获得最大的 like-time 系数 总和，应按照满意度升序做菜；满意度大的最后再做；满意度为负数的菜，可以选择做或者不做 // 大于等于0的菜必做，然后选择负数的菜作为第一道菜，看其能否使like-time系数 // 排序后倒序遍历：每增加一道菜like-time系数变化量为：satisfaction[i] +....+ satisfaction[n-1] Arrays.sort(satisfaction); int n = satisfaction.length; if (satisfaction[n - 1] <= 0) return 0; int sum = 0, res = 0; for (int i = n - 1; i >= 0; i--){ sum += satisfaction[i]; if (sum > 0){ res += sum; }else{ break; } } return res; } }
