Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm số lượng táo đã ăn tối đa bằng Python

Giả sử chúng ta có hai mảng được gọi là ngày và táo có cùng độ dài n. Có một loại cây táo đặc biệt, mỗi ngày đều trồng táo trong n ngày liên tục. Vào ngày thứ i, nó mọc ra số lượng táo [i] và sẽ bị thối sau ngày [i] ngày, vì vậy chúng ta có thể nói như vậy vào ngày thứ i + ngày [i] táo sẽ bị thối và không thể ăn được. Vào một số ngày. Nếu táo [i] =0 và ngày [i] =0, thì nó cho biết vào ngày thứ i, cây táo không mọc thêm quả táo nào. Chúng ta có thể ăn nhiều nhất một quả dứa mỗi ngày. (Chúng ta có thể tiếp tục ăn sau n ngày đầu tiên). Ở đây chúng ta phải tìm ra số lượng táo tối đa mà chúng ta có thể ăn.

Vì vậy, nếu đầu vào giống như táo =[1,2,3,5,2] ngày =[3,2,1,4,2], thì đầu ra sẽ là 7 vì -

  • Vào ngày thứ nhất, chúng ta ăn một quả táo đã lớn vào ngày đầu tiên.

  • Vào ngày thứ hai, chúng tôi ăn một quả táo đã lớn vào ngày thứ hai.

  • Vào ngày thứ 3, chúng ta ăn một quả táo đã lớn vào ngày thứ hai. Nhưng sau ngày này, những quả táo trồng vào ngày thứ ba sẽ bị thối rữa.

  • Vào các ngày từ 4 đến 7, chúng ta ăn táo đã mọc vào ngày thứ tư.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • minheap:=một heap trống mới
  • ngày:=0, res:=0
  • đối với tôi trong phạm vi từ 0 đến cỡ quả táo - 1, thực hiện
    • ngày:=i
    • trong khi minheap không trống và giá trị rot của đỉnh minheap - day, thực hiện
      • xóa phần tử trên cùng khỏi minheap
    • nbrApple:=apple [i]
    • hết hạn:=i + ngày [i] -1
    • nếu nbrApple> 0, thì
      • chèn cặp (expiration, nbrApple) vào minheap
    • nếu minheap không trống, thì
      • (date, apple):=phần tử trên cùng của minheap và xóa nó khỏi heap
      • res:=res + 1
      • nếu apple> 1, thì
        • chèn cặp (ngày, apple-1) vào minheap
  • trong khi minheap không trống, hãy thực hiện
    • ngày:=ngày + 1
    • while minheap không trống và giá trị rot của top of minheap
    • xóa phần tử trên cùng khỏi minheap
  • nếu minheap trống, thì
    • ra khỏi vòng lặp
  • (date, apple):=top of minheap và xóa nó khỏi heap
  • res:=res + 1
  • nếu apple> 1, thì
    • chèn cặp (ngày, apple-1) vào minheap
  • trả lại res

    • Ví dụ

    Hãy cùng chúng tôi xem cách 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