做菜顺序如何用贪心最大化满意度？为什么从高满意度往前加？
简化版
做菜顺序先把满意度排序，然后从大到小尝试把菜加到最前面。维护当前已选菜的满意度总和 sum，如果加入新菜后 sum + satisfaction[i] > 0，总收益会增加，就加入；否则继续加入只会让收益变差，可以停止。
详细版
排序后，高满意度菜应该尽量靠后，因为时间系数更大。反向遍历时，相当于把一个新菜插到当前序列最前面，所有已选菜的时间都会加 1，总收益增加量正好是“新加入后的满意度总和”。只要这个增量为正，就值得加入。
时间复杂度 O(n log n)，空间复杂度 O(1)。这题也能用动态规划，但贪心利用了排序后“从后往前扩展”的收益结构。
完整版教学
一、题目收益为什么和顺序强相关
每道菜的贡献是：
time * satisfaction同一道满意度为 5 的菜，放在第 1 个做贡献 5，放在第 3 个做贡献 15。满意度越高，越应该放在后面享受更大的时间系数。
[-1, 5]
顺序 [-1,5]：-1*1 + 5*2 = 9
顺序 [5,-1]：5*1 + -1*2 = 3所以先排序，让大的满意度有机会排到后面。
二、为什么从高满意度往前加
排序后，我们可以先选满意度最高的一批菜，并把它们按升序排列。反向遍历等价于不断把更小的菜插到最前面。
已选：[4, 5]
加入 2 到前面：[2, 4, 5]加入前，4 和 5 的时间分别是 1、2；加入后变成 2、3，它们的贡献都会增加一次自己的满意度。
记忆钩子：往前插一盘菜，所有已选菜都“多等一轮”，增量就是已选满意度总和。
三、增量为什么是新 sum
假设已有序列总满意度和为 sum。把新菜 x 插到最前面后：
新菜贡献：x * 1
旧菜每道时间 +1，总贡献额外增加：sum
总增量：x + sum加入后新的 sum 也正好是 sum + x。所以判断是否值得加入，只要看 sum + x > 0。
| 加入后 sum | 是否加入 |
|---|---|
| 正数 | 总收益增加 |
| 0 | 不增加收益，可不加 |
| 负数 | 总收益减少 |
四、为什么一旦不值得就可以停止
我们是从大到小往前遍历。若当前 x 加入后 sum + x <= 0，那么后面的数字只会更小，加入后的 sum 更不可能变正。
排序：[-9, -8, -1, 0, 5]
从 5 往前加
如果加 -8 已经不划算，再加 -9 更不划算这就是停止条件的贪心依据。
五、代码模板
int maxSatisfaction(int[] satisfaction) {
Arrays.sort(satisfaction);
int sum = 0, ans = 0;
for (int i = satisfaction.length - 1; i >= 0; i--) {
if (sum + satisfaction[i] <= 0) break;
sum += satisfaction[i];
ans += sum;
}
return ans;
}ans += sum 是因为每次往前插入一盘菜后，总收益增加量就是新的满意度总和。
六、用数字例子推演
satisfaction=[-1,-8,0,5,-9]，排序为：
[-9, -8, -1, 0, 5]从后往前：
加 5：sum=5, ans=5
加 0：sum=5, ans=10
加 -1：sum=4, ans=14
加 -8：sum=-4，不加，停止答案是 14，对应顺序 [-1,0,5]。
七、常见误区与追问
- 误区：把负数满意度全部丢掉。 有些负数放在前面能提高后面正数的时间系数，总收益反而增加。
- 误区：按绝对值排序。 贡献和满意度正负及时间位置有关，不是绝对值问题。
- 误区：
ans每次加当前菜贡献。 反向插入时总增量是新的sum，不是单个x。 - 追问：为什么高满意度放后面？ 后面时间系数更大，高满意度乘更大系数更划算。
- 追问：能用 DP 吗？ 可以，但排序后贪心更简洁，利用了增量单调性。
- 追问：为什么可以 break？ 后续数字更小，当前加入都不增益，后面更不可能增益。
八、加强记忆
做菜顺序的关键是“从后往前加菜”。高满意度菜放后面，反向遍历时每加一盘到前面，旧菜全体时间加一，收益增量就是加入后的满意度总和。sum+x 正就加，非正就停；负数不是一定坏，要看它能不能让后面的正数多乘一轮。