題目 : zerojudge p500. 礦沙背包問題

連結 : https://zerojudge.tw/ShowProblem?problemid=p500

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

程式碼如下 :

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,x=0,a,b; // 取 n 單位礦砂，有 m 種，用 x 累積價值
    cin >> n >> m;
    priority_queue <int,vector<int>,less<int>> aa; // 存單位礦砂的價格
    for (int i=0;i<m;i++){
        cin >> a >> b;  // 此時 a 為 wi ， b 為 pi
        for (int i=0;i<a;i++){
            aa.push(b); // 總共有 a(wi) 單位價值為 b(pi) 的礦砂
        } 
    }
    while(n--){  // 最多取出 n 單位礦砂
        if (aa.empty()) break; // 所有礦砂都被取出就結束
        x+=aa.top(); // 讀取目前礦砂價值中最大的並加到 x 
        aa.pop();  // 已經取出的礦砂要被拿走，以免重複取出
    }
    cout << x << endl;
}

判分結果 : AC (3ms, 764KB)
時間複雜度 :
裝入 : O(s log s) s 為礦砂總單位數 (即 wi 總和)
彈出礦砂 : O(n log s)