Python程序：查找构建k个相同高度塔楼所需的最小砖块数

假设我们有一列塔的高度，以及一个正值k。我们想要选择k个塔，通过添加更多的砖块使它们的高度相同，但要尽可能少地使用砖块。我们必须找到使k个塔的高度相同所需的最小砖块数。

因此，如果输入类似于heights = [4, 7, 31, 14, 40] k = 3，则输出将为17，因为我们可以选择5、8和15，这需要17块砖来使高度相同。

为了解决这个问题，我们将遵循以下步骤：

  • 对列表heights进行排序
  • ans := 无穷大
  • s := 0
  • 对于每个索引i和heights中的值x，执行以下操作：
    • s := s + x
    • 如果i >= k，则
      • s := s - heights[i - k]
    • 如果i >= k - 1，则
      • ans := ans 和 (x * k - s) 的最小值
  • 返回ans

让我们来看下面的实现，以便更好地理解：

示例

实时演示

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

更新于：2020年11月19日

427 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习
广告