각종 STL의 lower/upper_bound

set과 map에
algorithm header의 lower_bound와 upper_bound를 사용하면 O(N)으로 비효율적이다
set의 iterator는 양방향itr이기때문
그래서 set과 map에는 멤버함수로 lower_bound, upper_bound함수가 따로있다.

그래서 특정값이상을 찾아 erase가 잦은 경우 단지 erase가 잦다는 이유로 list를 택할 수 없다.
list에서 제공하는 lower_bound는 O(N)이고 erase가 O(1)인것을 감안해도 
set/multiset에 넣고 lower_bound하고 erase하는게 더 효율적일 수 있다.

관련문제 : https://www.acmicpc.net/problem/1202

 

정답코드)

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);

	int N, K;
	cin >> N >> K;

	vector<pair<int, int>> pq(N);
	int M, V;
	for (int i = 0; i < N; i++) {
		cin >> M >> V;
		pq[i] = { V, M };
	}
	sort(pq.begin(), pq.end(),
		[&](auto a, auto b) {
			if (a.first == b.first) return a.second < b.second;
			else return a.first > b.first;
		}
	);

	multiset<int> C;
	int input;
	for (int i = 0; i < K; i++) {
		cin >> input;
		C.insert(input);
	}

	long long answer = 0;
	int index = 0;
	while (index < N && C.size()) {
		int value = pq[index].first;
		int weight = pq[index].second;
		index++;

		auto itr = C.lower_bound(weight);
		if (itr != C.end()) {
			answer += value;
			C.erase(itr);
		}		
	}

	cout << answer;
	
	return 0;
}