Chương trình tìm số gạch tối thiểu để xây k tháp cùng chiều cao trong Python

Mô tả bài toán

Cho danh sách chiều cao tháp heights và số k. Chọn k tháp và thêm gạch để chúng cùng chiều cao, sử dụng ít gạch nhất. Tìm số gạch tối thiểu.

Ví dụ: heights = [5, 8, 32, 15, 41], k = 3 → đầu ra 17 (chọn 5,8,15 cần 17 gạch để đưa về 15).

Giải thuật (Cửa sổ trượt trên mảng đã sắp xếp)

1. Sắp xếp heights.
2. Khởi tạo ans = inf, s = 0 (tổng cửa sổ).
3. Duyệt i, x qua heights:
   • s += x.
   • Nếu i >= k: s -= heights[i-k].
   • Nếu i >= k-1: ans = min(ans, x*k - s).
4. Trả về ans.

Ví dụ mã Python

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