Hợp nhất tế bào trong Python

Cho danh sách cells đại diện kích thước tế bào. Mỗi vòng lặp, hai tế bào lớn nhất a, b tương tác:

• Nếu a == b: cả hai chết
• Ngược lại: hợp nhất thành tế bào mới kích thước floor((a+b)/3)

Tìm kích thước tế bào cuối cùng hoặc -1 nếu không còn tế bào.

Ví dụ: [20,40,40,30] → 16 (40,40 chết; 20,30 hợp nhất thành floor(50/3)=16).

Các bước giải quyết (dùng heap)

• Chuyển tất cả giá trị thành âm, tạo max-heap
• Khi heap còn >1 phần tử:
  • Lấy 2 phần tử lớn nhất (đổi dấu dương)
  • Nếu khác nhau: đẩy -((a+b)//3) vào heap
• Trả về -heap[0] nếu còn phần tử, ngược lại -1

Ví dụ mã Python

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))

Đầu vào

[20,40,40,30]

Đầu ra

16