백준 1781 컵라면 c++ // 우선순위큐 정렬방법, 선택x인경우 처리방법

https://www.acmicpc.net/problem/1781

1781번: 컵라면

1. 우선순위큐 정렬방법

매개변수가 같으면 false를 리턴해야함에 주의하자.

class cmp {
public:
	bool operator () (pair<ll, ll> p1, pair<ll, ll> p2) {
		if (p1.first == p2.first) {
			return p1.second < p2.second;
		}
		return p1.first > p2.first;
	}
};

 

2. 문제점

기한순 정렬후 최대컵라면 뽑는방법 -> 기한을 선택안하는경우가 최적이면 오답

 

3. 해결(선택x인경우 처리방법) 

ansQ.top과 cur을 비교한다.

1.오름차순 ansQ를 선언한다

2. 데드라인이내 -> ansQ에넣기, day++

    데드라인초과 -> 직전데드라인의 컵라면을 선택할지말지 결정한다 -> 이후 해당날짜의 컵라면을  확정한다.

            : (ans.top < cur) -> 직전데드라인의 컵라면을 선택안하는게 이득임 -> ans에서 25를뺴고 100을넣는다

            : 아닌경우 -> 직전데드라인 선택하는게 이득임(그대로)

   1일차의 컵라면이 100으로 확정된다.

 3. ansQ에 딱 n일만큼의 컵라면이 담긴다.                          

 

4. 전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class cmp {
public:
	bool operator () (pair<ll, ll> p1, pair<ll, ll> p2) {
		if (p1.first == p2.first) {
			return p1.second < p2.second;
		}
		return p1.first > p2.first;
	}
};
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>,cmp> pq;
priority_queue<ll, vector<ll>, greater<int>> pqans;

ll n,ret;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		ll a, b;
		cin >> a >> b;
		pq.push({ a,b });
	}

	/*while (pq.size()) {
		cout << pq.top().first << " " << pq.top().second << "\n";
		pq.pop();
	}*/

	int day = 1;
	while (pq.size()) {
		auto cur = pq.top(); pq.pop();
		//데드라인중 최대값을 ans큐에 넣는다
		if (day <= cur.first) {
			pqans.push(cur.second);
			day++;
		}
		else {
			//같은데드라인중 더작은값은 자동으로패스됨
			//이전데드라인(ans.top)을 선택하지않는것이 최적인경우
			if (pqans.top() < cur.second) {
				pqans.pop();
				pqans.push(cur.second);
			}
		}
	}

	while (pqans.size()) {
		ret += pqans.top();
		pqans.pop();
	}

	cout << ret;
	return 0;
}