보석 도둑

문제 한 줄 요약 :

비싼 보석을 tight하게 가방에 넣기

( tight하게라는 말은 최대한 많은 보석을 가방에 넣어야 하기 때문에

-> 보석의 무게와 [같거나 작으면서 제일 근접한] 무게의 가방에 넣기

==> lower_bound 사용함 )

 

배운 점 :

1. priority_queue<구조체,vector<구조체>> 사용할 수 있고, < 도 오버라이딩할 수 있음 (사실 여기서 pq를 안 써도 됨 왜냐하면 처음부터 끝까지 보석을 뽑기 때문에 굳이 pq 쓸 필요 없다고 함)

2. multiset

 - multiset_name.lowerbound(value)

 - insert,erase(iter or value)

 

#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;

ll N,K;
multiset<ll> C;
ll ans;

struct boseok {
	ll M;
	ll V;
};

struct compare{
	bool operator()(const boseok& a, const boseok& b){
		return a.V < b.V;
	}
};

priority_queue<boseok,vector<boseok>,compare> pq;

int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	cin>>N>>K;
	
	for(int i = 0; i < N; i++){
		ll M,N; cin>>M>>N;
		pq.push({M,N});
	} 
	for(int i = 0,a; i < K; i++) {cin>>a; C.insert(a);}
    
	int bag = K;
	while(!pq.empty()){	

		ll a = pq.top().M, b = pq.top().V;
		pq.pop();
		auto idx = C.lower_bound(a);
		if(*idx >= a){ // if(idx != C.end())
		ans += b;
		bag--;
		C.erase(idx);
		}
        if(bag == 0) break;
	}
	cout<<ans;
	return 0;
}