(1202) 보석 도둑

https://www.acmicpc.net/problem/1202

단계별로 풀어보기

26단계(우선순위 큐) 6번째

 

 

 

가방마다 보석은 하나씩만 넣을 수 있으므로, 그리디하게 이 가방에 넣을 수 있는 보석 중 가장 비싼 보석을 넣는 것이 좋다.

최대 무게가 큰 가방이 항상 유리하므로, 최대 무게가 작은 가방부터 하나씩 탐색하면 된다. 이때 가방에 넣을 수 있는 보석 중 가장 비싼 보석은 우선순위 큐(최대 힙)를 이용하면 빠르게 찾을 수 있다.

보석을 무게 순으로 오름차순으로 정렬한 뒤 최대 무게가 가벼운 가방부터 가방을 탐색할 때마다 이 가방에 들어갈 수 있는 보석의 가격을 전부 우선순위 큐에 넣는다. 전부 넣은 뒤 우선순위 큐의 top이 지금 가방에 넣을 수 있는 가장 비싼 보석이다.

 

 

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> p;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  
  cin >> n >> k;
  
  vector<p> a(n);
  vector<int> b(k);
  priority_queue<int> pq;
  
  for(int i=0;i<n;i++)  cin >> a[i].first >> a[i].second;
  for(int i=0;i<k;i++)  cin >> b[i];
  
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  
  int x= 0;
  long ans= 0;
  
  for(int i=0;i<k;i++){
    while(x<n && a[x].first<=b[i]){
      pq.push(a[x].second);
      x++;
    }
    
    if(!pq.empty()){
      ans+= pq.top();
      pq.pop();
    }
  }
  
  cout << ans;
  
  return 0;
}