做菜顺序

难度: Hard

一个厨师收集了他 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

Submission

运行时间: 16 ms

内存: 16.1 MB

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        ans, tmp = 0, 0
        for i in satisfaction:
            if tmp + i > 0:
                tmp += i
                ans += tmp
            else:
                break
        return ans

Explain

首先对满意度数组进行逆序排序，确保最大的满意度在前。然后迭代排序后的数组，逐步计算包含当前菜的总满意度乘积。如果加上当前菜的满意度后的总和依然为正，则继续累加该菜，否则停止添加更多的菜。这种方法是基于贪心算法的思想，总是尝试添加满意度最大的菜，以最大化最终的like-time系数总和。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        # 将满意度数组逆序排序
        satisfaction.sort(reverse=True)
        ans, tmp = 0, 0  # 初始化最终答案和当前的临时和
        for i in satisfaction:
            if tmp + i > 0:
                tmp += i  # 更新临时和
                ans += tmp  # 累加到最终答案
            else:
                break  # 如果添加当前菜后不再增加，停止迭代
        return ans  # 返回最终的like-time系数总和

Explore

选择对满意度数组进行逆序排序是为了确保在计算过程中首先考虑最大的满意度。因为总满意度是每道菜的满意度与其顺序的乘积，满意度大的菜先考虑可以保证总满意度的增加最为显著。若采用正序排序，较小的满意度值会先被计算，这可能导致在后面遇到高满意度菜时，由于累积的乘积效应减弱而无法最大化总满意度。

根据题解的贪心策略，一旦当前菜的累加导致总和为负，就会停止添加更多的菜。确实，这种方法可能会错过某些最优的组合，其中一些初始累加可能导致总和为负，但后续的高满意度菜可能会带来更大的总满意度。然而，贪心策略在很多情况下能提供有效且实施简单的解决方案，尽管它不保证总是最优。

贪心算法的正确性在此题中没有严格的理论证明，因为贪心算法通常是基于局部最优选择来期望达到全局最优解。在实际应用中，通过大量的测试数据来验证算法的有效性是常用的方法。具体到这个问题，可以通过设计多种包含不同满意度值和顺序的测试案例，来观察算法是否能够得到预期的高满意度总和，从而间接验证算法的有效性。如果在多数情况下结果接近最优，那么可以认为贪心算法是有效的。