[BOJ] 19580 마스크가 필요해

(2021년 1월 21일에 작성한 글입니다.)

 

19580번: 마스크가 필요해

20 Summer SUAPC Div 2에서 이 문제 처음 봤는데

범위가 최대 10^18인걸 보고 대회때는 그냥 패쓰했다

그때 당시에는 수 범위가 큰 거는 그냥 패스하자는 마인드가 있었어서 패쓰했는데

​

두 달쯤 전에 이거 다시 풀었었는데

잘 모르겠어서 결국 풀이를 봤고,

풀이대로 했는데도 계속 틀려서 미뤄뒀던 문제

​

근데 다시 보니까 두 달 전에 틀렸던 이유는

내가 multimap을 썼는데, key 값에 대해 원소를 삭제하면

multimap에 있는 모든 원소가 삭제된다는 걸 몰랐다.

예를 들어

multimap<int, int> arr;

arr.insert({1, 1});

arr.insert({1, 2});

arr.erase(1);

하면 arr에는 아무것도 남지 않게 된다...

​

근데 그냥 map을 쓰면 되는데 왜 그때 multimap으로 했는지 모르겠다...

여튼

​

풀이는

최대 지불 금액이 작은 순으로, 같다면 최소 지불 금액이 큰 순으로 정렬하고

구매할 수 있는 마스크를 lower_bound로 찾아서

마스크가 있다면 사면 된다.

​

회의실 배정 문제와 비슷하지만 다르다.

그 문제도 그렇고 이것도 그렇고

떠올리기가 쉽지 않다..

bool sortby(pair<ll, ll> a, pair<ll, ll> b) {
	if (a.second == b.second) {
		return a.first > b.first;
	}
	return a.second < b.second;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, M;
	ll ans = 0;
	int i, j;

	cin >> N >> M;
	vector<pair<ll, ll>> money(N + 5);
	map<ll, ll> mask;
	for (i = 0; i < N; i++) {
		cin >> money[i].first >> money[i].second;
	}
	sort(money.begin(), money.begin() + N, sortby);

	for (i = 0; i < M; i++) {
		ll a, b; cin >> a >> b;
		mask[a] += b;
	}

	for (i = 0; i < N; i++) {
		auto iter = mask.lower_bound(money[i].first);
		if (iter != mask.end() && iter->first <= money[i].second) {
			if (--iter->second == 0) {
				mask.erase(iter->first);
			}
			ans++;
		}
	}

	cout << ans << ENDL;

	return 0;
}