Posted on 2023-03-29 18:04
Uriel 阅读(32)
评论(0) 编辑 收藏 引用 所属分类:
贪心 、
闲来无事重切Leet Code
给出一些菜品的满意值，可以选择做其中的0~所有菜，最后总的满意度计算方式为sum(time[i] * satisfaction[i])，time[i]=i是指该道菜是第i个做的，贪心，越满意的菜品越后做，这样time[i]更大
实际做的时候将菜品按满意度从大到小排序，不断累加满意度值，如果到某一时刻累加值为负，后面的菜都不用考虑了
1 #1402
2 #Runtime: 16 ms (Beats 100%)
3 #Memory: 13.5 MB (Beats 70.27%)
4
5 class Solution(object):
6 def maxSatisfaction(self, satisfaction):
7 """
8 :type satisfaction: List[int]
9 :rtype: int
10 """
11 satisfaction.sort(reverse=True)
12 ans, tp = 0, 0
13 for i in range(len(satisfaction)):
14 tp += satisfaction[i]
15 if tp < 0:
16 break
17 ans += tp
18 return ans