โปรแกรมหาอิฐน้อยสุดสร้าง k หอคอยสูงเท่ากันใน Python

สมมติว่ามีรายการความสูงหอคอย heights และค่า k ต้องการเลือก k หอคอยและเติมอิฐให้สูงเท่ากัน ใช้อิฐน้อยที่สุด

ตัวอย่าง: heights = [5, 8, 32, 15, 41], k = 3 ผลลัพธ์ 17 เลือก 5, 8, 15 ใช้ 17 อิฐ

ขั้นตอนการแก้ปัญหา

1. เรียง heights
2. ans = inf, s = 0
3. วน i, x ใน enumerate(heights):
   • s += x
   • ถ้า i >= k: s -= heights[i-k]
   • ถ้า i >= k-1: ans = min(ans, x*k - s)
4. คืน 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