Pythonで最大の建物の高さを見つけるプログラム

値nと、制限と呼ばれるペアの別のリストがあるとします。都市にn棟の新しい建物を建てたいと思っています。ただし、制限はほとんどありません。私たちは一列に建てることができ、建物には1からnまでのラベルが付けられています。制限には2つのパラメーターがあるため、restrictions [i] =（id_i、max_height_i）は、id_iの高さがmax_height_i以下でなければならないことを示します。新しい建物の高さに関する市の制限は次のとおりです-

• 各建物の高さは0または正の値である必要があります。

• 最初の建物の高さは0でなければなりません。

• 隣接する2つの建物の高さの差は1を超えることはできません。

最も高い建物の可能な限り高い高さを見つける必要があります。

したがって、入力がn =5、restrictions =[[2,1]、[4,3]]の場合、可能な最大の高さを見つける必要があるため、出力は4になります。したがって、次のように4にすることができます。図。

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

• 制限が空の場合、

  • n-1を返す

• resi：=IDに基づいてリストの制限を並べ替える

• k：=0

• idx：=1

• resiの各reについて、実行します

  • re [1]：=re [1]と（k + re [0] -idx）の最小値

  • k：=re [1]

  • idx：=re [0]

• k：=resiの最後の要素の最大高さ

• idx：=resiの最後の要素のID

• リストを逆にする

• 最初のアイテム以降のresiの各reについて、実行します

  • re [1]：=re [1]と（k-re [0] + idx）の最小値

  • k：=re [1]

  • idx：=re [0]

• リストを逆にする

• f：=0

• idx：=1

• res：=0

• resiの各reについて、実行します

  • ff：=（f + re [0] -idx）およびre [1]

    の最小値

  • res：=resの最大値と（re [0] --idx + f + ff）/2の商

  • idx：=re [0]

  • f：=ff

• （f + n-idx）とresの最大値を返します

例

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

def solve(n, restrictions):
   if not restrictions:
      return n-1
   resi = sorted(restrictions, key = lambda x:x[0])

   k = 0
   idx = 1
   for re in resi:
      re[1] = min(re[1], k+re[0]-idx)
      k = re[1]
      idx = re[0]
   k = resi[-1][1]
   idx = resi[-1][0]
   resi.reverse()
   for re in resi[1:]:
      re[1] = min(re[1], k-re[0]+idx)
      k = re[1]
      idx = re[0]
   resi.reverse()

   f = 0
   idx = 1
   res = 0
   for re in resi:
      ff = min(f+re[0]-idx, re[1])
      res = max(res, (re[0] - idx + f + ff) // 2)
      idx = re[0]
      f = ff
   return max(f+n-idx,res)

n = 5
restrictions = [[2,1],[4,3]]
print(solve(n, restrictions))

入力

5, [[2,1],[4,3]]

出力

4