[C++] 백준 1826번 연료 채우기

문제

백준 1826번 연료 채우기

풀이

기름 보유량이 많은 주유소에서만 주유해야 주유소에 최대한 덜 방문하고 도착할 수 있다.

현재보유한 기름으로 갈 수 있는 한계까지 최대한 이동하며 지나온 각 주유소의 보유연료를 maxheap에 담는다. 더이상 이동할 수 없을 때 지금까지 지나온 주유소중 연료가 가장 많았던 곳을 택해 기름을 채운다. 마을에 도착할 때까지 반복하되 도착할 수 없을 경우 -1을 출력하면 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>
#define endl '\n'

using namespace std;

int n,des,noil;
vector<pair<int,int>> v;
priority_queue<int> maxheap;

int solve(){
  int cnt = 0;

  for (int i=0; i<=n; i++){
    while (v[i].first > noil) {
      if (maxheap.empty()) return -1;

      noil += maxheap.top();
      maxheap.pop();
      cnt++;
    }

    maxheap.push(v[i].second);
  }
  return cnt;
}

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

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  for (int i=0; i<n; i++){
    int a,b;
    cin >> a >> b;

    v.push_back({a,b});
  }

  cin >> v[n].first >> noil;

  sort(v.begin(), v.end());

  cout << solve();
}