题解-做菜顺序-排序,贪心,前缀和,一点点证明

, , , 评论

Problem: 1402. 做菜顺序

思路

  • 注意到没有要求顺序,先排序
  • 朴素思想是将大的数越往后放越好,但对于负数,虽然也是越大越往后放越好,但其有可能增加答案,也有可能减少答案,需要一些证明

解题方法

  • 注意到对于负数的选取一定是连续而非跳跃的:假设存在数组,三者均小于0,假如一定要取两个元素,(这种假定的含义是我需要后面的正数有足够的倍数,期望前面提供倍数的负数(代价)最小),选取元素代价大于选取
  • 推广可知我们会选取所有的正数和部分负数,且负数在排序后的数组中是连续的,并且和正数部分相连
  • 实际上是求一个子数组的这个操作最大能多大,可以枚举每一次从哪选,结束一定是在最大的数结束
  • 然后简化:注意到相关操作实际上是对于之前结果再加上一次已经遍历的数,所以可以将其转化为一遍扫描的方式

时间复杂度,

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True) #方便操作
        res=0
        pre=0
        now=0
        for num in satisfaction:
            pre+=num
            now+=pre
            res=max(now,res)
            if now<0:
                break #之后一定小于0
        return res

Noirking's Pawn

个人简介。