สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums เราสามารถลดความยาวของ nums ได้โดยการเอาตัวเลขสองตัวใดๆ ก็ตาม ลบออกแล้วผนวกผลรวมในตอนท้าย ค่าใช้จ่ายในการดำเนินการนี้คือผลรวมของจำนวนเต็มสองตัวที่เราลบออก เราต้องหาต้นทุนรวมขั้นต่ำของการลดจำนวนลงเหลือหนึ่งจำนวนเต็ม
ดังนั้นหากอินพุตเป็นเหมือน nums =[2, 3, 4, 5, 6] ผลลัพธ์จะเป็น 45 เนื่องจากเราเอา 2 และ 3 ออกแล้วเอาออกเพื่อให้ได้ [4, 5, 6, 5] เราก็ เอา 4 และ 5 ออกแล้วเอาออกเพื่อรับ [6, 5, 9] จากนั้นเอา 6 และ 5 จากนั้นเอาออกและเราได้ [9, 11] และสุดท้ายลบ 9 และ 11 เราจะได้ 19 ดังนั้นผลรวมคือ 45.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างฮีปโดยใช้องค์ประกอบที่มีอยู่ในจำนวน
- ตอบ :=0
- ในขณะที่ขนาดของ nums>=2 ทำ
- a :=องค์ประกอบสูงสุดของ heap nums
- b :=องค์ประกอบสูงสุดของ heap nums
- ans :=ans + a + b
- แทรก a+b ลงใน heap nums
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution: def solve(self, nums): import heapq heapq.heapify(nums) ans = 0 while len(nums) >= 2: a = heapq.heappop(nums) b = heapq.heappop(nums) ans += a + b heapq.heappush(nums, a + b) return ans ob = Solution() nums = [2, 3, 4, 5, 6] print(ob.solve(nums))
อินพุต
[2, 3, 4, 5, 6]
ผลลัพธ์
45
