백준[1202] 보석 도둑

문제 설명

문제 링크

http://icpc.me/1202

1202번: 보석 도둑

풀이

그리디로 풀 수 있다.

보석의 정보를 보석의 가격을 기준으로 내림차순으로 정렬한다.

그 후에 처음부터 가격이 높은 것부터 차례대로 무게보다는 크거나 같은 최소 가방을 찾으며 가방을 매칭 시켜주면 된다. 

가방을 매칭시켜줄때는 lower_bound를 이용하면 된다.

또한 가방을 매칭시키고 바로 없애주기 위해 multiset 자료구조를 사용한다.

cf) 모든 보석을 담을 수 있다면 최대 3*10^5 * 10^6으로 int형 범위를 넘어간다.

코드

#include <cstdio>
#include <set>
#include <algorithm>

using namespace std;
using ll = long long;

pair<int, int> arr[300005];
multiset<int> m;

int main() {
    int n, k; scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d %d", &arr[i].first, &arr[i].second);
    for (int i = 0; i < k; i++) {
        int k; scanf("%d", &k);
        m.insert(k);
    }
    sort(arr, arr + n, [](const auto &a, const auto &b) { 
        if (a.second == b.second) return a.first < b.first;
        return a.second > b.second; 
    });
    ll ans = 0;
    for (int i = 0; i < n; i++) if (!m.empty()) {
        auto [f, s] = arr[i];
        auto iter = m.lower_bound(f);
        if (iter != m.end()) {
            ans += s;
            m.extract(*iter);
        }
    }
    printf("%lld", ans);
}