2109번: 순회강연

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


$O(nlgn)$

(di,pi)를 데드라인 기준으로 오름차순 정렬한 뒤 다음 그리디 알고리즘을 적용한다.
1. pi를 스케줄에 넣는다.
2. 현재 스캐줄이 불가능한 경우(즉, 일 개수>di) 스케줄 안에 p가 작은 일을 제거한다.

이 알고리즘의 정당성을 증명하기 위해 2번에 귀류법을 적용한다.
그 당시 제거한 이익을 px라 하자. px<=pi 일 것이다.
최종 스케줄 상에 pi 대신 px가 들어갔을 때 더 높은 수익을 얻을 수 있는 경우는 없으므로 증명 완료.

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int n, r;
pair<int, int> p[10000];
priority_queue<int> pq;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &p[i].second, &p[i].first);
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        r += p[i].second;
        pq.push(-p[i].second);
        if (pq.size() > p[i].first) r += pq.top(), pq.pop();
    }
    printf("%d", r);
    return 0;
}