สมมติว่าเรามีรายการตัวเลขที่เรียกว่าเซลล์ รายการนี้แสดงขนาดของเซลล์ต่างๆ ในการวนซ้ำแต่ละครั้ง เซลล์ที่ใหญ่ที่สุดสองเซลล์ a และ b มีปฏิสัมพันธ์ตามกฎเหล่านี้:ดังนั้น ถ้า a =b เซลล์ทั้งสองตาย มิฉะนั้น เซลล์ทั้งสองจะผสานกันและขนาดของเซลล์จะกลายเป็นพื้นของ ((a + b) / 3) เราต้องหาขนาดของเซลล์สุดท้ายหรือคืนค่า -1 หากไม่มีเซลล์เหลืออยู่
ดังนั้นหากอินพุตเป็น [20,40,40,30] เอาต์พุตจะเป็น 16 ในการวนซ้ำครั้งแรก 40 และ 40 จะตาย จากนั้น 20 และ 30 จะกลายเป็นชั้นของ ((20+30) / 3) =ชั้น 50/3 =16
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เซลล์ :=แปลงค่าแต่ละค่าของอาร์เรย์เซลล์เป็นค่าลบ
-
สร้างกองกับเซลล์
-
ในขณะที่เซลล์ไม่ว่างให้ทำ -
-
ลบสององค์ประกอบออกจากเซลล์และแปลงเป็นค่าลบอีกครั้ง และกำหนดให้เป็นอันดับแรกและครั้งที่สองติดต่อกัน
-
-
ถ้าตัวแรกไม่เท่ากับวินาที −
-
แทรกค่าลบของพื้นของ (แรก+วินาที)/3) ลงในฮีป
-
-
ส่งกลับค่าลบของเซลล์[0] ถ้าเซลล์มีองค์ประกอบอย่างอื่น - 1
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
from heapq import heapify, heappop, heappush class Solution: def solve(self, cells): cells=[-x for x in cells] heapify(cells) while len(cells)>1: first,second = -heappop(cells), -heappop(cells) if first!=second: heappush(cells, -((first+second)//3)) return -cells[0] if cells else -1 ob = Solution() cells = [20,40,40,30] print(ob.solve(cells))
อินพุต
[20,40,40,30]
ผลลัพธ์
16
