#45250: 解題方法


lbm00138 (A是蘋果 B是香蕉)

學校 : 臺北市立成淵高級中學
編號 : 270386
來源 : [223.23.153.125]
最後登入時間 :
2025-09-01 13:30:59

此題類似於 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 的錯誤。

 

https://hackmd.io/@-NK1yL0aSQS4GGo6S9IfeQ/SJKavTodkx

#53346: Re: 解題方法


rsj00008 (西加008)

學校 : 基隆市私立二信高級中學
編號 : 49436
來源 : [114.24.22.164]
最後登入時間 :
2025-10-08 12:16:07

不用這麼麻煩吧!
從最貴重的開始取,取夠n個{或取光}就是答案
排序後
價   重     還可取? n     ,取後總值
4     5         20                     5*4  = 20
3    10        20-5                10*3  + 20 = 50
2     20       15-10               5*2  + 50 = 60