プライオリティキュー

プライオリティキュー

プライオリティキュー を使って、下記の問題を解いてみます。

[問題]

車で 距離L の道を移動します。車にはもともとガソリンが P はいっています。

この車では距離１走るとガソリンが１消費されます。ガソリンが０になると車は停止し移動は失敗します。

途中には N箇所 のガソリンスタンドがあり、各ガソリンスタンドは道のスタート地点からそれぞれ 距離Ai の地点にあり Bi だけガソリンを補給することができます。

車の燃料タンクにはいくらでもガソリンを補給できます。

車は最後まで移動できるでしょうか。最後まで移動できる場合は 最小の補給回数 を、移動できない場合は -1 を出力してください。

[条件]

・ガソリンスタンド数Nは、1以上10000以下です。
・目的とする移動距離Lと初期ガソリン量は、1以上1000000以下です。
・スタート地点から各ガソリンスタンドまでの距離Aiは、1以上目的とする移動距離L以下です。
・各ガソリンスタンドで補給できるガソリン量Biは、1以上100以下です。

[解き方]

車で走るときには、ガソリンスタンドの場所に来た時にしかガソリンを補給できません。

しかし ガソリンスタンドの場所に来た時、それ以降いつでも一度だけガソリンを補給できる権利を手に入れる というように考えることもできます。

後で補給したくなった時に、すでに通過したガソリンスタンドで補給していたことにします。

できるだけ少ない回数の補給にしたいので、燃料が０になるまで走ってから補給をすることにします。

燃料が０になったときに使うべきガソリンスタンド（ガソリン量）は、明らかに最も大きいガソリン量です。

これを効率的に行うために、大きい数字から順に取り出せる プライオリティキュー を使います。


通常のリスト型から max関数 で一番補給量の多いものを取得し、取得したら remove関数 でその要素を削除することで プライオリティキュー の機能を実現します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#------------入力例１-----------------
L = 25  # 距離[L]
P = 10  # 初期ガソリン量[P]
# 各ガソリンスタンド（４か所）までの 距離[Ai] と ガソリン補給量[Bi]
stands = [{'A':10,'B':10}, {'A':14,'B':5}, {'A':20,'B':2}, {'A':21,'B':4}]
#-------------------------------------
cnt = 0   # 補給回数
pos = 0   # 現在の位置（スタート地点からの距離）
tank = P  # 現在の保有ガソリン量
lst = []  # ガソリンを補給できる権利（通り過ぎたガソリンスタンドで補給できたはずのガソリン量）

# 目的とする移動距離をガソリンスタンド管理データ[stands]に追加（補給はしないのでガソリン量は0）
stands.append({'A':L,'B':0})

for stand in stands:    # 移動箇所（各スタンド＋目的移動距離）分ループでまわす
  d = stand['A'] - pos  # このポイントまでの距離

  while tank - d < 0:   # 現在のガソリン量でスタンドまでたどり着けるかどうか
    # ガソリンが足りない場合
    if len(lst) > 0:    # ガソリン補給の権利があるかどうか
      x = max(lst)      # 一番補給量の多いものを取得（プライオリティキー機能として）
      lst.remove(x)     # 一番補給量の多いものを削除（プライオリティキー機能として）
      tank += x         # ガソリンを補給
      cnt += 1          # ガソリン補給回数をカウントアップ
    else:               # ガソリン補給ができない
      cnt = -1          # 移動失敗
      break

  if cnt < 0:           # 移動失敗したので終了
    break
  else:                 # 移動成功
    tank -= d           # タンクのガソリンを移動距離分減らす
    pos = stand['A']    # 現在位置をガソリン位置まで移動 
    lst.append(stand['B'])  # 到達したガソリンスタンドのガソリン補給可能量を権利としてリストに追加

print(cnt)

[実行結果]

2

１つめのと２つ目のガソリンスタンドでガソリンを補充すると目的の距離まで走ることができ、かつ最小の補給回数なので 2 が解となります。