[백준 1826] 연료 채우기

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

1L에 1km씩 갈 수 있고, 목적지까지 갈 수 있냐의 문제.

N 이 10000밖에 되질 않아서 DP로도 풀린다.

그리디는 글쎄 생각이 나질 않는다.

이 문제는 우선순위 큐로 풀었는데,

우선 주유소를 거리를 기준으로 sort하고(문제가 약았다)

내가 갈 수 있는 범위 내의 주유소의 기름을 max heap에 다가 넣어 준다.

그리고 max heap의 첫 번째의 기름을 더해서 내가 갈 수 있는 범위를 늘리며, 

그 기름양은 pop해준다.

그 범위 안에 있는 모든 주유소의 기름양을 max heap에 넣는다.

그리고 다시 max heap 첫 번 째 기름을 더해서 내가 갈 수 있는 범위를 늘리며 그 기름양은 pop하는 것을 반복한다.

최종적으로 목적지의 거리만큼 나의 기름양이 누적되었으면, 성공! 기름을 더해준 횟수를 출력.

안되면 -1을 출력한다.

#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
 
int n;
int nowGas, destDist;
class station {
public:
    int gas, dist;
    station() {};
    station(int gas, int dist) : gas(gas), dist(dist) {}
    bool operator <(station& cmp) {
        return this->dist < cmp.dist;
    }
};
 
station st[10001];
int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &st[i].dist , &st[i].gas);
    }
 
    sort(st, st + n);
    scanf("%d%d", &destDist, &nowGas);
 
    priority_queue<int> pq;
    int maxIdx = 0, num = 0;
    while (true) {
        if (nowGas >= destDist) break;
 
        while (maxIdx < n && st[maxIdx].dist <= nowGas){
            pq.push(st[maxIdx].gas);
            maxIdx++;
        }
        if (pq.empty()) break;
 
        nowGas += pq.top();
        pq.pop();
        num++;
    }
    
    if (nowGas < destDist) {
        cout << -1 << endl;
    }
    else {
        cout << num << endl;
    }
    return 0;
}