一、题目
链接
题面
一个厨师收集了他 n 道菜的满意程度 satisfaction ,这个厨师做出每道菜的时间都是 1 单位时间。
一道菜的 「喜爱时间」系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度,也就是
time[i]·satisfaction[i] 。请你返回做完所有菜 「喜爱时间」总和的最大值为多少。
你可以按 任意 顺序安排做菜的顺序,你也可以选择放弃做某些菜来获得更大的总和。
范围
n == satisfaction.length
1 <= n <= 500
-10^3 <= satisfaction[i] <= 10^3
样例
输入:satisfaction = [-1,-8,0,5,-9]
输出:14
解释:去掉第二道和最后一道菜,最大的喜爱时间系数和为 (-1·1 + 0·2 + 5·3 = 14) 。每道菜都需要花费 1 单位时间完成。
输入:satisfaction = [4,3,2]
输出:20
解释:按照原来顺序相反的时间做菜 (2·1 + 3·2 + 4·3 = 20)
输入:satisfaction = [-1,-4,-5]
输出:0
解释:大家都不喜欢这些菜,所以不做任何菜可以获得最大的喜爱时间系数。
输入:satisfaction = [-2,5,-1,0,3,-3]
输出:35
二、解法
假设一共选了N道菜,收益是:
∑ i = 1 n i ⋅ S i \sum_{i=1}^{n} i·S_{i} i=1∑ni⋅Si
那么很显然,由排序不等式可知,把 S \ S S 从小到大排序后的收益最大。
现在假设又新增一道菜 S 0 \ S_{0} S0 如何确保能让答案更大呢?
现在答案变成:
∑ i = 0 n ( i + 1 ) ⋅ S i \sum_{i=0}^{n} (i+1)·S_{i} i=0∑n(i+1)⋅Si
有:
∑ i = 0 n ( i + 1 ) ⋅ S i − ∑ i = 1 n i ⋅ S i = ∑ i = 0 n S i \sum_{i=0}^{n} (i+1)·S_{i}-\sum_{i=1}^{n} i·S_{i}=\sum_{i=0}^{n} S_{i} i=0∑n(i+1)⋅Si−i=1∑ni⋅Si=i=0∑nSi
也就是新增了 ∑ i = 0 n S i \sum_{i=0}^{n} S_{i} ∑i=0nSi 的值,只要 ∑ i = 0 n S i > 0 \sum_{i=0}^{n} S_{i}>0 ∑i=0nSi>0 就可以取这个 S 0 \ S_{0} S0 。
同时,每次新增完的答案可以写成:
∑ i = n 0 ∑ j = i n S i \sum_{i=n}^{0} \sum_{j=i}^{n} S_{i} i=n∑0j=i∑nSi
注意有 ∀ i < j , S i < S j \ \forall i<j , S_{i}<S_{j} ∀i<j,Si<Sj
令 p r e = ∑ j = i n S i \ pre=\sum_{j=i}^{n} S_{i} pre=∑j=inSi
所以,我们可以先给 s a t i s f a c t i o n \ satisfaction satisfaction 数组排个序,从大到小把 S i \ S_{i} Si 加进 p r e \ pre pre,如果 p r e > 0 \ pre>0 pre>0 , 再把它加进 a n s \ ans ans。
三、代码
#by concyclics
class Solution:
def maxSatisfaction(self, satisfaction) -> int:
satisfaction.sort(reverse=True)
ans=0
pre=0
for x in satisfaction:
pre+=x
if pre<=0:
break
ans+=pre
return ans
S=Solution()
print(S.maxSatisfaction([-2,5,-1,0,3,-3]))
真的蛮简单的。