此題類似於 0-1 背包,但物品可以只拿走部分,因此不需要動態規劃,用貪心演算就可以解決。
解題思路 :
1. 先設一個可以讀取最大值的 priority_queue ( 存單位礦砂的價格 ),及一個變數 x = 0 ( 累積的價值 )
2. 因為本題的 m ( 1 < m < 100 )和 wi ( 1 < wi < 1000 )都很小,所以當輸入各種礦砂的個數 wi 及單位價值 pi 時,可以先在 priority_queue 中放入 wi 個 pi 。( 此時 priority_queue 最多只有 100000 個數 )
3. 持續用 top() 讀取最大值加到 x 中並彈出 ( 貪心法,選擇價值最高的礦砂 ),重複 n 次。但要注意當所有礦砂的取完時( 即 priority_queue 為空時 )停止取出,否則會因為彈空棧而發生 RE 的錯誤。
不用這麼麻煩吧!
從最貴重的開始取,取夠n個{或取光}就是答案
排序後
價 重 還可取? n ,取後總值
4 5 20 5*4 = 20
3 10 20-5 10*3 + 20 = 50
2 20 15-10 5*2 + 50 = 60