1826번: 연료 채우기

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


$O(n\lg n)$

현재까지 지나쳐온 주유소 중 가장 많은 연료를 가진 주유소를 들렸던 것으로 여기고 이를 도착할 때까지 반복한다.

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