题解-做菜顺序-排序,贪心,前缀和,一点点证明
Problem: 1402. 做菜顺序 思路 注意到没有要求顺序,先排序 朴素思想是将大的数越往后放越好,但对于负数,虽然也是越大越往后放越好,但其有可能增加答案,也有可能减少答案,需要一些证明 解题方法 注意到对于负数的选取一定是连续而非跳跃的:假设存在$[a_{i-1},a_i,a_{i+1}].a_i<a_{i+1},$数组,三者均小于0,假如一定要取两个元素,(这种假定的含义是我需要后面的正数有足够的倍数,期望前面提供倍数的负数(代价)最小),选取元素$a_{i-1},a_{i+1}$代价大于选取$a_i,a_{i+1}$ 推广可知我们会选取所有的正数和部分负数,且负数在排序后的数组中是连续的,并且和正数部分相连 实际上是求一个子数组的这个操作最大能多大,可以枚举每一次从哪选,结束一定是在最大的数结束 然后简化:注意到相关操作实际上是对于之前结果再加上一次已经遍历的数,所以可以将其转化为一遍扫描的方式 时间复杂度, $O(nlogn)$ Code 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