パルクールアーティストがPythonで到達できる最も遠い建物を見つけるためのプログラム

さまざまな高さの家がn個あり、パルクールの芸術家がレンガやはしごを使って家から家へと移動したいとします。家の高さは配列として私たちに与えられます。各レンガの高さは単位の長さであり、それらのいくつかが与えられます。はしごとレンガは1回しか使用できません。パルクールの芸術家が行くことができる最も遠い建物を見つける必要があります。

したがって、入力が高さ=[5、8、7、6、2、3、1、4]、ブリック=3、ラダー=2のような場合、出力は7になります。

アーティストは0を構築することから始めます。

彼は3つのレンガの助けを借りて1号館に到着します。

後継の建物は前の建物よりも短いため、彼は建物2、3、4にジャンプします。

彼ははしごを使って4号館から5号館に移動します。

6号館の方が短いので、5号館から6号館にジャンプします。

彼は最後のはしごを使って7号館に到着します。

これを解決するには、次の手順に従います-

• temp：=新しいヒープ

• 1から高さのサイズまでの範囲のiの場合、実行します

  • dist：=heights [i] --heights [i-1]

  • dist> 0の場合、

    • れんが：=れんが-dist

    • 値をプッシュ-ヒープ温度まで遠ざける

    • れんが<0の場合、

      • はしご：=はしご-1

      • レンガ：=レンガ-ヒープ温度から削除された最小の要素

      • れんが<0またははしご<0の場合、

        • i-1を返す

• 高さの戻りサイズ-1

例

理解を深めるために、次の実装を見てみましょう-

from heapq import heappush, heappop
def solve(heights, bricks, ladders):
   temp = []
   for i in range(1, len(heights)):
      dist = heights[i] - heights[i - 1]
      if dist > 0:
         bricks -= dist
         heappush(temp, -dist)
         if bricks < 0:
            ladders -= 1
            bricks -= heappop(temp)
            if bricks < 0 or ladders < 0:
               return i - 1
   return len(heights) - 1

print(solve([5, 8, 7, 6, 2, 3, 1, 4], 3, 2))

入力

[5, 8, 7, 6, 2, 3, 1, 4], 3, 2

出力

7