BOJ)1202 보석 도둑

문제: icpc.me/1202

가장 가격이 많이 나가는 보석을 최대한 많이 담아야 원하는 답을 구할 수 있는건 그리디하게 알 수 있다.

그렇기 때문에 우리는 가장 가격이 많이 나가는 보석을 먼저 보며 lower_bound를 이용하여 현재 그 보석을 담을 수 있는 가방이 있느지 확인해주면 된다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
int n, k, x, y;
long long r;
int main() {
    scanf("%d%d", &n, &k);
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &x, &y);
        pq.push({ y,x });
    }
    multiset<int> ms;
    for (int i = 0; i < k; i++) {
        scanf("%d", &x);
        ms.insert(x);
    }
    while (pq.size()) {
        int cost = pq.top().first;
        int pay = pq.top().second;
        pq.pop();
        auto it = ms.lower_bound(pay);
        if (it == ms.end())
            continue;
        ms.erase(it);
        r += cost;
    }
    printf("%lld\n", r);
    return 0;
}