BOJ 1826号燃料充填パイ

質問する

聖書はトラックをジャングルに運転し,トラックのタンクに突然穴が開き,1キロ走ると1 Lの燃料が漏れた.これを直すために、一番近い村に行かなければなりません.しかし、まっすぐ行くと、途中で燃料が尽きる可能性があります.幸いなことに、ジャングルのあちこちにNのガソリンスタンドが燃料をいっぱい入れることができます.しかしジャングルで途中停車するのは危険な行為なので、できるだけガソリンスタンドに停車する回数を減らします.
幸いなことに,聖書のトラックは良いので,燃料タンクには燃料の制限がなく,たくさん入れることができます.各ガソリンスタンドの位置と各ガソリンスタンドで得られる燃料量が与えられるタイミングで、各ガソリンスタンドの駐車回数を求めるプログラムを作成してください.
ジャングルは直線で、聖書のトラックもガソリンスタンドも直線上にあります.ガソリンスタンドは聖書のトラックを基準に右側にあります.

入力

1行目はガソリンスタンドの個数N(1≦N≦10000)を与え、2行目からN+1行目はガソリンスタンドの情報を与える.ガソリンスタンドの情報は2つの整数a,bからなり,a(1≦a≦1000000)は聖書の開始位置からガソリンスタンドまでの距離を表し,b(1≦b≦100)はガソリンスタンドが満たす燃料量を表す.そしてN+2行には2つの整数LとPがあり,L(1≦L≦1000000)は聖書の位置から村までの距離,(1≦L≦1000000)である. P≦1000000)は、トラック上の既存燃料の量を意味する.

しゅつりょく

1行目はガソリンスタンドの停止回数を印刷します. 村に行けない場合は、-1を印刷します.

import heapq

n = int(input())
gs = []
#최소힙
for _ in range(n):
    dist,f = map(int,input().split())
    heapq.heappush(gs,[dist,f])
#최대힙
target,fuel = map(int,input().split())

filled = []
cnt = 0

#종료조건: 종점과 fuel이 같아지거나 fuel이 더 커졌을 때
while target>fuel:

		#현재 fuel로 갈 수 있는 거리의 gas들을 최소힙에서 빼내서 전부 move라는 최대힙에 넣음
    while gs and gs[0][0]<=fuel:
        dist, f = heapq.heappop(gs)
				# -1을 곱해주어서 최대힙으로 사용
				# 최대힙에 넣는 이유는 문제에서 주유소에서 멈추는 횟수를 최소화하라고 하기 때문에, 가능한한
				#	기름을 많이 채울 수 있는 주유소에서 채우기 위함
        heapq.heappush(filled,-1*f)
    #주유소에서 기름을 다 채웠거나, 아니면 주유소는 남았는데 현재 fuel로 해당 주유소들에 도달할 수 
		#없을 경우에는 종점까지 못 가므로 -1을 print하고 종료 
    if not filled:
        cnt = -1
        break
    #최대힙에서 빼낸 기름을 현재 fuel에 더해주고, 주유소에 멈췄으므로 count
    f = heapq.heappop(filled)
    fuel += -1*f
    cnt+=1

print(cnt)

正しい方法を思いついたが、簡単には実現しなかった.
優先順位キューは頭の中に現れなかったため,それを用いて解くことなく実現が複雑になった.
他の人の解説を見て、理解してから、私のコードで体現しました.
概念の理解と簡単な問題の使用を超えて、様々な状況に適した方法を体験し、熟知しなければならない.