Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-03-29 19:15:45
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:
作者: Firstshadow (IamCatづミ'_'ミづ)   2023-03-29 19:30:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com