Chương trình tìm số táo ăn được tối đa trong Python

Giả sử có hai mảng days và apples cùng độ dài n. Cây táo đặc biệt mọc táo n ngày liên tiếp. Ngày i mọc apples[i] quả, hỏng sau days[i] ngày (ngày i + days[i] đã hỏng). Nếu apples[i] = 0 và days[i] = 0 thì ngày i không mọc táo. Mỗi ngày chỉ ăn được tối đa 1 quả (có thể ăn sau n ngày). Tìm số táo ăn được tối đa.

Ví dụ: apples = [1,2,3,5,2], days = [3,2,1,4,2], đầu ra = 7.

• Ngày 1: ăn táo ngày 1
• Ngày 2: ăn táo ngày 2
• Ngày 3: ăn táo ngày 2 (táo ngày 3 hỏng sau ngày này)
• Ngày 4-7: ăn táo ngày 4

Giải pháp

Sử dụng min-heap (hàng đợi ưu tiên) lưu (ngày hết hạn, số lượng), luôn ăn táo sắp hết hạn nhất:

• minheap := heap rỗng, day := 0, res := 0
• Với i từ 0 đến len(apples)-1:
  • day := i
  • Khi minheap không rỗng và minheap[0][0] < day: pop (bỏ táo hỏng)
  • nbrApple := apples[i], expiration := i + days[i] - 1
  • Nếu nbrApple > 0: push (expiration, nbrApple) vào minheap
  • Nếu minheap không rỗng:
    • (date, apple) := pop minheap
    • res += 1
    • Nếu apple > 1: push (date, apple-1) vào minheap
• Khi minheap không rỗng (sau n ngày):
  • day += 1
  • Bỏ táo hỏng (minheap[0][0] < day)
  • Nếu minheap rỗng: break
  • Pop, res += 1, push lại nếu còn > 1
• Trả về res

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

import heapq

def solve(apples, days):
    minheap = []
    heapq.heapify(minheap)
    day = 0
    res = 0
    for i in range(len(apples)):
        day = i
        while minheap and minheap[0][0] < day:
            heapq.heappop(minheap)
        nbrApple = apples[i]
        expiration = i + days[i] - 1
        if nbrApple > 0:
            heapq.heappush(minheap, (expiration, nbrApple))
        if minheap:
            date, apple = heapq.heappop(minheap)
            res += 1
            if apple > 1:
                heapq.heappush(minheap, (date, apple - 1))
    while minheap:
        day += 1
        while minheap and minheap[0][0] < day:
            heapq.heappop(minheap)
        if minheap == []:
            break
        date, apple = heapq.heappop(minheap)
        res += 1
        if apple > 1:
            heapq.heappush(minheap, (date, apple - 1))
    return res

apples = [1,2,3,5,2]
days = [3,2,1,4,2]
print(solve(apples, days))

Đầu vào

[1,2,3,5,2], [3,2,1,4,2]

Đầu ra

7