Re: [閒聊] 每日LeetCode已回收
1402. Reducing Dishes
給你一個陣列satisfaction表示第i個餐點的滿意度，定義滿意係數為：滿意度[i]*時間，
廚師可以決定是否要做某個菜以及做菜的先後順序，求出廚師可得的最大滿意係數。
Example:
Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total
like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.
Example 2:
Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
思路：
1.要取得最佳解要時間和滿意度越大越好，所以我們先把所有的滿意度排序。
2.反向思考，從滿意度最大的餐點開始拿如果當前的sum大於0表示第一個做的菜
為正數可以使解變更佳，關鍵為每次把res加總到sum時都會把先前拿的值多加
一倍。
Java Code：
-----------------------------------------------
class Solution {
public int maxSatisfaction(int[] satisfaction) {
Arrays.sort(satisfaction);
int n = satisfaction.length;
int res = 0;
int sum = 0;
for (int i = n - 1; i >= 0; i--) {
sum += satisfaction[i];
if (sum < 0) break;
res += sum;
}
return res;
}
}
-----------------------------------------------
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680088548.A.75F.html
→
03/29 19:30,
2年前
, 1F
03/29 19:30, 1F
討論串 (同標題文章)
完整討論串 (本文為第 275 之 719 篇)：