題目連結:
題目意譯:
一位主廚蒐集了一些他對於 n 道料理的滿意程度之數據。該主廚在一單位時間可以做出任意一道料理。
一道料理的「好時」係數(原文:Like-time Coefficient)定義為做出該料理的時間(包含前面的料理)乘以其滿意程度,即 time[i] × satisfaction[i]。
回傳藉由準備若干道料理後,該主廚可以達到的最大好時係數之總和值。
這些料理可以按任意順序製作,也可以捨棄若干道料理來使主廚得到這個最大值。
限制:
n == satisfaction.length
1 ≦ n ≦ 500
-1000 ≦ satisfaction[i] ≦ 1000
範例測資:
範例 1:
輸入: satisfaction = [-1,-8,0,5,-9]
輸出: 14
解釋: 在移除第二道與最後一道料理之後,最大好時係數總和將等於 (-1×1 + 0×2 + 5×3 = 14)。
每一道料理各自都會在一單位時間內完成。
範例 2:
輸入: satisfaction = [4,3,2]
輸出: 20
解釋: 這些料理可以按任意順序製作,(2×1 + 3×2 + 4×3 = 20)
範例 3:
輸入: satisfaction = [-1,-4,-5]
輸出: 0
解釋: 人們不喜歡這些料理。主廚將不準備任何一道料理。
解題思維:
可以看到最佳解中每一道料理的滿意程度必定將會是以非嚴格遞增之順序排列,即越早做的滿意程度越低、越晚做的滿意程度越高。因為時間的係數是固定的,而為了最大化總和就只能將滿意程度大的配上時間係數大的。
因此我們可以先將 satisfaction 中的數字由小排到大。
接著我們可以從範例測資 1 看到最佳解不一定只有挑出滿意程度是正的那些料理,因為有幾個小的負滿意程度的料理存在可以把正滿意程度大之時間係數變大,而這可能反而會比較好。
所以我們先當作所有料理都要做,因而算出一個包含著所有料理的好時係數總和 LT。此時在過程中順便求出一個所有料理滿意程度之總和 S(等下會用到)。
可以看到在「必定要做恰好 n 道料理」(即全部的料理)的情況下,最佳解就是 LT。那 n - 1 道呢?我們可以移除哪一道料理?
答案很簡單,移除最一開始做的那一道料理即可,因為其滿意程度是最低的。因此最佳解為 LT - S(因為少了一道料理,這意味著每一道料理的時間係數將都統一減去 1,而總體被減去的總和恰好為 S)。
此時將 S 減去第一道料理的滿意程度,我們便得到在「必定要做恰好 n - 1 道料理」的情況下的最佳解以及這 n - 1 道料理的滿意程度之總和。
因此我們可以重複上述的論述直到把所有料理的移除光光為止。
而所求的「真」最佳解即是
「必定要做恰好 n 道料理」的最佳解、
「必定要做恰好 n - 1 道料理」的最佳解、
……
「必定要做恰好 1 道料理」的最佳解、
「必定要做恰好 0 道料理」的最佳解(此值必為 0)。
上述各自的最佳解中的最大值。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。