Pythonで同じ高さのk個の塔を作るために必要なレンガの最小数を見つけるためのプログラム

塔の高さのリストと正の値kがあるとします。 k個のタワーを選択し、レンガを追加してすべて同じ高さにしますが、使用するレンガはできるだけ少なくします。 k個の塔を選び、同じ高さにするために必要なレンガの最小数を見つける必要があります。

したがって、入力がheights =[4、7、31、14、40] k =3のような場合、出力は17になります。これは、5、8、および15を選択できるため、同じ高さを作成するには17個のブリックが必要です。 。

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

• リストの高さを並べ替える
• ans：=無限大
• s：=0
• 高さの各インデックスiと値xについて、実行します
  • s：=s + x
  • i> =kの場合、
    • s：=s-高さ[i-k]
  • i> =k-1の場合、
    • ans：=最小のansおよび（x * k-s）
• 回答を返す

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

例

class Solution:
   def solve(self, heights, k): heights.sort()
      ans = float("inf")
      s = 0
      for i, x in enumerate(heights):
         s += x
         if i >= k:
            s -= heights[i - k]
         if i >= k - 1:
            ans = min(ans, x * k - s)
      return ans
ob = Solution()
heights = [5, 8, 32, 15, 41]
k = 3
print(ob.solve(heights, k))

入力

[5, 8, 32, 15, 41], 3

出力

17