Giả sử chúng ta có một danh sách các chiều cao của tháp, và một giá trị dương k. Chúng tôi muốn chọn k tháp và làm cho tất cả chúng có cùng chiều cao bằng cách thêm nhiều viên gạch hơn, nhưng sử dụng càng ít viên gạch càng tốt. Chúng ta phải tìm số lượng gạch tối thiểu cần thiết để chọn k tháp và làm cho chúng có cùng chiều cao.
Vì vậy, nếu đầu vào giống như heights =[4, 7, 31, 14, 40] k =3, thì đầu ra sẽ là 17, vì chúng ta có thể chọn 5, 8 và 15, yêu cầu 17 viên gạch để tạo cùng chiều cao .
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- sắp xếp các độ cao của danh sách
- ans:=infinity
- s:=0
- đối với mỗi chỉ số i và giá trị x theo chiều cao, hãy thực hiện
- s:=s + x
- nếu tôi> =k, thì
- s:=s - heights [i - k]
- nếu tôi> =k - 1, thì
- ans:=tối thiểu ans và (x * k - s)
- trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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)) Đầu vào
[5, 8, 32, 15, 41], 3
Đầu ra
17