BOJ)1826 연료 채우기

문제:icpc.me/1826

1km를 가는데 1L의 연료가 필요하고 현재 가진 연료량과 목적지까지의 거리 그리고 각 주유소의 정보가 주어질 때 충전횟수를 최소화하여 목적지에 도착하는 충전횟수를 출력하는 문제이다.

우선 주유소의 정보를 받아 거리를 기준으로 sort한 뒤 내가 현재 갈 수 있는 거리보다 가까운 거리에 있는 모든 주유소의 정보를 받아와 채울 수 있는 연료량을 heap에 저장한다. 이후 그리디하게 갈 수 있는 주유소중 가장 큰 연료량을 가지는 주유소를 선택해나가면 문제를 해결 할 수 있다.

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