백준 1202 보석 도둑 혼내주기

 

 

 

knapsack의 냄새가 나지만 속지않고 그리디로 담을 수 있는 무게가 가장 작은 가방부터 담을 수 있는 최고 가격의 보석을 담으면 된다는 것, 우큐를 사용하면 되겠다 까지 떠올렸는데, 어떻게 구현할지 떠올리지 못했다...

가장 작은 가방부터 담을 수 있는 모든 보석을 우큐에 넣고, 하나씩 꺼내면 된다.

정렬 문제가 은근 약한 것 같다. 예전에 백준의 Q-인덱스 문제도 못풀고, 프로그래머스에서 똑같은 문제를 또 못푼게 기억이 난다... 아무래도 정렬 문제를 복습해야 겠다...

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

pii arr[300005];
int bags[300005];
int n, k;

void input() {
    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin >> arr[i].first >> arr[i].second;
    for(int i = 0; i < k; ++i) cin >> bags[i];
}

int main() {
    fastio;
    input();

    sort(arr, arr+n);
    sort(bags, bags+k);

    priority_queue<int> pq;
    ll ans = 0;
    for(int i = 0, idx = 0; i < k; ++i) {
        while(idx < n && arr[idx].first <= bags[i]) {
            pq.push(arr[idx++].second);
        }
        if(!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans;
}