---

1402. 做菜顺序

• 标签：贪心、数组、动态规划、排序
• 难度：困难

题目链接

• 1402. 做菜顺序 - 力扣

题目大意

描述：给定一个数组 $satisfaction$，表示每道菜的满意值。可以按任意顺序做菜，每道菜只能做一次。时间是 $1, 2, 3, \dots$ 递增。

总喜爱时间 = $\sum_{i=1}^{t} satisfaction[i] \times i$，其中 $t$ 是做的菜的数量。也可以选择不做某些菜。

要求：返回最大总喜爱时间。

说明：

• $1 \le satisfaction.length \le 500$。
• $-1000 \le satisfaction[i] \le 1000$。

示例：

• 示例 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)

解题思路

思路 1：贪心 + 排序

1. 核心思想

将满意值大的菜放在后面做（时间系数大），负满意值的菜尽量放在前面或不做。

排序后，从后往前考虑。每次增加一道菜时，新的总时间 = 旧的总时间 + 新菜值 + 之前的累积和（因为所有后面的菜时间都 $+1$）。

具体地，排序后从后往前遍历，用 $cur$ 表示当前做的菜的总和（累积），$total$ 表示当前总喜爱时间。

2. 具体步骤

第 1 步：降序排序 $satisfaction$（从大到小）。

第 2 步：遍历排序后的数组，$cur = 0, total = 0$。

• 如果 $cur + s > 0$：加上这道菜能增加总时间。
  • $cur += s$
  • $total += cur$（所有已选菜的时间系数 $+1$，加上新菜）
• 否则跳过（后续更小的值也不会使结果更大）。

第 3 步：返回 $total$。

3. 正确性证明

贪心策略证明：排序从大到小考虑，每次加入能提升总值的菜。因为满意度大的菜放后面系数大，所以从大到小排序后从后向前取。加入一道新菜会使所有已有的菜的时间系数 $+1$，增量 = $cur + s$（新菜在时间 $1$ 加上，已有菜各 $+s$）。如果增量 $> 0$ 就加。

4. 举例说明

以 $satisfaction = [-1, -8, 0, 5, -9]$ 为例：

排序：$[5, 0, -1, -8, -9]$

• $s=5$：$cur=0$，$cur+s=5>0$，$cur=5$, $total=5$
• $s=0$：$cur+s=5>0$，$cur=5$, $total=10$
• $s=-1$：$cur+s=4>0$，$cur=4$, $total=14$
• $s=-8$：$cur+s=-4\le0$，跳过
• $s=-9$：跳过

结果：$14$。

验证：做 $5,0,-1$ 三道菜，安排顺序 $-1,0,5$ → $(-1)\times1 + 0\times2 + 5\times3 = -1+0+15=14$ ✓

思路 1：代码

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        total = 0
        cur = 0
        for s in satisfaction:
            if cur + s > 0:
                cur += s
                total += cur
        return total

思路 1：复杂度分析

• 时间复杂度：$O(n \log n)$，排序。
• 空间复杂度：$O(1)$。