[1826] 연료 채우기

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

1826번: 연료 채우기

<문제>

도달할 수 있는 주유소의 연료를 전부 큐에 넣는다.

큐가 비었다는 것은, 도착지에 도다를 수 없음을 의미하니 -1을 출력하고

그렇지 않을때에는 충전할 수 있는 연료의 최대값만큼을 충전한다.

int s;의 의미는 '현재까지의 연료의 총 량'이자, '갈 수 있는 주유소의 범위'다.

하나의 주유소에서 여러번 주유하는 일이 없도록, 22라인처럼 최악의 경우일때 선형으로 push하도록 구현하면

한 주유소에서 여러번 주유하는 부분을 자연스럽게 처리할 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
vector<pi> v;
priority_queue<int> q;
int n, l, s, ans;
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    v.resize(n);
    int i;
    for (i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    cin >> l >> s;
    sort(v.begin(), v.end());
    int idx = 0;
    while (1) {
        if (s >= l) {
            cout << ans;
            return 0;
        }
        while (idx < n && v[idx].first <= s) q.push(v[idx++].second);
        if (q.empty()) break;
        s += q.top();
        q.pop();
        ans++;
    }
    cout << -1;
    return 0;
}