P1208 [USACO1.3]混合牛奶 Mixing Milk

哈夫曼编码之后做的第二个贪心题...

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 5010;

#define PII pair<int, int>
#define int long long

PII a[N];
int n, m;

signed main(){
    cin >> n >> m;
    
    for(int i = 0; i < m; i ++) cin >> a[i].first >> a[i].second;
    
    sort(a, a + m);
    
    int res = 0;
    for(int i = 0; i < m; i ++){
        if(a[i].second >= n){
            res += n * a[i].first;
            break;
        }
        res += a[i].first * a[i].second;
        n -= a[i].second;
    }
    
    cout << res << endl;
    
    return 0;
}