Posted on 2023-03-29 18:04
Uriel 閱讀(47)
評論(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