สมมติว่าเรามีรายการความสูงของหอคอย และค่าบวก k เราต้องการเลือก k ทาวเวอร์ และทำให้สูงเท่ากันโดยเพิ่มอิฐมากขึ้น แต่ใช้อิฐให้น้อยที่สุด เราต้องหาจำนวนอิฐขั้นต่ำที่จำเป็นในการเลือก k ทาวเวอร์ และทำให้สูงเท่ากัน
ดังนั้นหากอินพุตเท่ากับความสูง =[4, 7, 31, 14, 40] k =3 แล้วผลลัพธ์จะเป็น 17 เนื่องจากเราสามารถเลือก 5, 8 และ 15 ซึ่งต้องใช้อิฐ 17 ก้อนเพื่อให้ได้ความสูงเท่ากัน .
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- จัดเรียงความสูงของรายการ
- แทน :=อินฟินิตี้
- s :=0
- สำหรับแต่ละดัชนี i และค่า x ในความสูง ทำ
- s :=s + x
- ถ้าฉัน>=k แล้ว
- s :=s - ความสูง[i - k]
- ถ้าฉัน>=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
ผลลัพธ์
17
