Python에서 같은 높이의 타워를 만드는 데 필요한 최소 벽돌 수를 찾는 프로그램

<시간/>

타워 높이 목록과 양수 값 k가 있다고 가정합니다. 우리는 k개의 타워를 선택하고 더 많은 벽돌을 추가하여 가능한 한 적은 수의 벽돌을 사용하여 모두 같은 높이로 만들고 싶습니다. k개의 타워를 골라 같은 높이로 만드는 데 필요한 최소 벽돌 수를 찾아야 합니다.

따라서 입력이 heights =[4, 7, 31, 14, 40] k =3과 같으면 출력은 17이 됩니다. 동일한 높이를 만들기 위해 17개의 벽돌이 필요한 5, 8, 15를 선택할 수 있기 때문입니다. .

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

목록 높이 정렬
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