BOJ 2019 - 순회강연(Greedy)

www.acmicpc.net/problem/2109

2109번: 순회강연

- 짧게 걸리면서 페이가 높은 순으로 강연을 해야 가장 높은 수익을 올릴 수 있다. 현재 소요기간을 카운트하기 위해서 우선순위 큐를 이용해서 시행한 강연만 페이에 대한 최대힙에 남도록 로직을 구현했다. 

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n, ans;
vector<pair<int, int>> a;
priority_queue<int> pq;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        int pay, day;
        cin >> pay >> day;
        a.push_back({day, -pay});
    }
    sort(a.begin(), a.end());  // day 오름차순, pay 내림차순

    for (int i = 0; i < n; ++i) {
        ans -= a[i].second;
        pq.push(a[i].second);

        if (a[i].first >= pq.size()) continue;  // pq.size()는 현재 소요기간
        ans += pq.top();
        pq.pop();
    }

    cout << ans;
    return 0;
}