[BOJ 1826]満タン燃料

質問する
[BOJ 1826]満タン燃料
1キロ離れたところに1リットルの燃料が漏れている.
ジャングルのあちこちにN個のガソリンスタンドが燃料をいっぱい入れることができます.
ガソリンスタンドで村に着くまで停止回数を求めます(できるだけ少なくしなければなりません)
に答える
ガソリンスタンドを通るたびに.
今すぐ行けるガソリンスタンドなら、一番大きなお尻に置きます.
reside<0は、現在ガソリンスタンドが燃料不足で到着できないため、従来のガソリンスタンドから給油する必要があることを示しています.(以前のガソリンスタンドで最も燃料が多かったガソリンスタンドを選択)
村までの距離はLで固定されているので、村から一番近いガソリンスタンドを選ぶのはx
停止回数を最小限に抑えるには、燃料量の大きいガソリンスタンドを選択しなければなりません
コード#コード#

import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N = int(input()) #  주유소의 개수 N(1 ≤ N ≤ 10,000)
stations = []
for _ in range(N):
    a,b = map(int,input().split()) # 1 ≤ 시작 위치~주유소 거리 ≤ 1,000,000, 1 ≤ 주유소에서 채울수있는 연료의 양 ≤ 100
    stations.append((a,b))
stations.sort()
L,P = map(int,input().split()) # 1 ≤ 성경~마을 거리 ≤ 1,000,000, 1 ≤ 트럭에있던 연료의 양 ≤ 100
stations.append((L,0))

pos = 0
remain = P
reserve = []
ans = 0
'''
# 주유소 지날 때마다 reserve 힙에 넣기
# remain<0이면 (과거 주유소에서) 기름 충전하기
'''
for (dist,fuel) in stations: #노트1
    remain -= dist-pos
    while remain<0:
        if not reserve: print(-1); exit(0)
        remain += -heappop(reserve)
        ans += 1
    heappush(reserve, -fuel) # 현재 도달 가능한 주유소를 힙에 넣음
    pos = dist
print(ans)

ノート
すべてのガソリンスタンドを調査する