1402. Reducing Dishes¶
题目信息¶
- 题号:
1402
- 难度:
Hard
- 主题:
贪心、排序、前缀和
- 原题:
- 重点:
可以舍弃任意菜并重新排序;第
i道完成的菜贡献satisfaction * i,最大化总和
题目重述¶
给定数组 satisfaction,其中每个元素表示一道菜的满意度。可以选择任意子集并按任意顺序烹饪,烹饪每道菜耗时一个单位。
若一道菜在第 i 个时间单位完成,其贡献为 satisfaction * i,时间从 1 开始。请返回所有选择与排列方案中最大的总满意度;允许一道菜都不做并得到 0。
1 <= satisfaction.length <= 500,-1000 <= satisfaction[i] <= 1000。
自建示例¶
适当保留负满意度菜也可能提高总和:
输入:satisfaction = [-2,5,-1]
输出:11
解释:按 -2、-1、5 的顺序烹饪,贡献为 -2 - 2 + 15 = 11。
全部满意度为负时选择空集:
输入:satisfaction = [-2,-1]
输出:0
解释:制作任意非空菜集都会得到负总和。