급하게임개발

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;
}