문제에 dead line이 있고 그 문제를 dead line 안에 해결하면 컵라면이 주어진다.
문제를 푸는데는 1이 걸리며 최대로 받을 수 있는 컵라면의 개수를 구하는 문제다.
greedy하게 해결할 수 있다.
dead line을 오름차순으로 정렬하고 받을 수 있는 컵라면 개수는 내림차순으로 정렬해보자.
현재 시간이 지금 컵라면의 dead line보다 작거나 같으면 min heap에 삽입한다.
위의 경우가 아니고 min heap의 top값이 현재 컵라면의 개수보다 작으면
min heap의 top값과 현재 컵라면의 개수를 서로 교환해준다.
이것이 성립하는 이유는 현재 min heap에 들어있는 컵라면들의 dead line이
현재 컵라면의 dead line보다 작거나 같음이 보장되기 때문이다.
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct Cup {
int dead, num;
};
int N;
Cup cup[200001];
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%d%d", &cup[n].dead, &cup[n].num);
sort(cup, cup + N, [](Cup &a, Cup &b)->bool {
return a.dead == b.dead ? a.num > b.num : a.dead < b.dead;
});
priority_queue<int> pq;
int cnt = 1;
int ans = 0;
for (int n = 0;n < N;n++) {
if (cnt <= cup[n].dead) {
cnt++;
pq.push(-cup[n].num);
ans += cup[n].num;
}
else if (!pq.empty() && -pq.top() < cup[n].num) {
ans += (cup[n].num + pq.top()); //top은 빼주고 cup은 더해준다.
pq.pop();
pq.push(-cup[n].num);
}
}
printf("%d\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기