BOJ 1202 보석도둑

www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

재밌었다.

어차피 각 가방에 하나씩밖에 안 들어간다는 뜻이니까, 들어갈 수 있는 보석의 가격을 최대힙(STL-priority_queue)으로 저장한 다음, 더 이상 안 들어가면 최대 가격을 ans에다 저장해주면 되는 문제였다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(0);
	cout.tie(0);
	int N, K;
	cin >> N >> K;
	int index = 0;
	priority_queue<int> Q;
	vector<pair<int, int>> Marr;
	vector<int> Karr;
	long long ans=0;
	for (int i = 0; i < N; i++)
	{
		pair<int, int> tmp;
		cin >> tmp.first >> tmp.second;
		Marr.push_back(tmp);
	}
	for (int i = 0; i < K; i++)
	{
		int tmp;
		cin >> tmp;
		Karr.push_back(tmp);
	}
	sort(Marr.begin(), Marr.end());
	sort(Karr.begin(), Karr.end());
	for (int i = 0; i < K; i++)
	{
		while (index < N && Marr[index].first <= Karr[i])
		{
			Q.push(Marr[index].second);
			index++;
		}
		if(!Q.empty())
		{
			ans += Q.top();
			Q.pop();
		}
		
	}
	cout << ans;
	return 0;
}

그런데 왜 글 작성 할 때는 예쁘게 보이는게 올리면 구려질까? 알 수가 없다.