https://www.acmicpc.net/problem/1202
이 문제의 경우 Priority Queue를 사용하지 않으면 시간 초과 가 발생한다 이문제의 핵심은 작은 가방에 담을수 있는 가장 큰걸 담고 그다음크기의 가방에 그 가방의 크기에 담을 수 있는것중 가장 큰것을 담으면 된다.
이 로직을 구현하기 위해서는 일차적으로 가장 작은 무게에 담을 수 있는 모든 물건들을 선택한다 거기서 가장 큰 애를 선택한다. 이차적으로 이전에 담고 남은 물건들중에 두번째 무게에 담을 수 있는 모든 물건들을 모두 고른 후 이전 애 고른애들과 합쳐서 놓은 다음 그중에 큰거를 고르면 된다.
이 로직에서 일단 필요한건 우선순위 큐다. 일차적으로 가방을 작은 순으로 나열해서 가장 작은 가방에 담을 수 있는 애를 우선순위큐에 담는다 보석들도 무게순으로 정렬 되어 있다 그래서 첫번째 가방에 담으면 첫번째 가방에 담긴 마지막 인덱스 이후로 무게가 큰 보석들이 남는다 그중 두번째 가방에 닿을 수 있는 물건들을 담아서 우선순위 큐에 넣는다. 거기서 최고 큰값을 선택 한다
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
priority_queue<int> pq;
int bag[300000];
pair<int, int> jewerly[300000];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
int temp1, temp2;
cin >> temp1 >> temp2;
jewerly[i] = { temp1,temp2 };
}
for (int i = 0; i < k; i++) {
cin >> bag[i];
}
sort(jewerly, jewerly + n);
sort(bag, bag + k);
int idx=0;
long long sum = 0;
for (int i = 0; i < k; i++) {
while (idx < n && bag[i] >= jewerly[idx].first) {
pq.push(jewerly[idx].second);
idx++;
}
if (!pq.empty()) {
sum += pq.top();
pq.pop();
}
}
cout << sum;
}
