백준 1202 보석 도둑

백준 1202

이 문제의 알고리즘은 다음과 같다.
1. 보석의 가격을 1순위로 해서 가격과 무게를 내림차순 정렬을 한다
2. set에 가방의 최대 무게들을 담는다.
3. set의 lower_bound 함수를 이용해서 각 보석의 무게를 감당할 수 있는 최소한의 가방을 선택한다.

ex) 3 2
1 65
5 23
2 99
10
2
보석의 무게가 2일 때 , lower_bound에 넣으면 10이 아닌 최대 2의 무게를 가질 수 있는 가방이 선택된다.

#include <bits/stdc++.h>
#include<set>
using namespace std;
int n, k;
vector<pair<int,int>> v;
multiset<int> s;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> k;

	while (n--) {
		int a, b;
		cin >> a >> b;
		v.push_back({ b,a });
	}
	sort(v.begin(), v.end(),greater<>());
	while (k--) {
		int x;
		cin >> x;
		s.insert(x);
	}
	long long ans = 0;
	for (auto c : v) {
		if (s.empty()) break;
		if (s.lower_bound(c.second) == s.end()) continue;
		else ans += c.first;
		s.erase(s.lower_bound(c.second));
	}
	cout << ans << '\n';
}