โปรแกรมหาจำนวนแอปเปิ้ลที่กินสูงสุดใน Python

สมมติว่าเรามีสองอาร์เรย์ที่เรียกว่าวันและแอปเปิ้ลที่มีความยาวเท่ากัน n มีต้นแอปเปิ้ลชนิดพิเศษที่ปลูกแอปเปิ้ลทุกวันเป็นเวลา n วันติดต่อกัน ในวันที่ i มันเติบโตจำนวนแอปเปิ้ล [i] จำนวนแอปเปิ้ลและที่จะเน่าหลังจากวัน [i] ดังนั้นเราสามารถพูดเช่นนั้นในวันที่ i + วัน[i] แอปเปิ้ลจะเน่าและไม่สามารถกินได้ ในบางวัน. หาก apples[i] =0, และ days[i] =0 แสดงว่าในวันที่ i ต้นแอปเปิลไม่มีแอปเปิลใดๆ เราสามารถทานแอปเปิลได้มากที่สุดหนึ่งผลต่อวัน (เราสามารถกินต่อได้หลังจาก n วันแรก) ที่นี่เราต้องหาจำนวนแอปเปิ้ลสูงสุดที่เรากินได้

ดังนั้น หากอินพุตเป็นเหมือนแอปเปิ้ล =[1,2,3,5,2] วัน =[3,2,1,4,2] ผลลัพธ์จะเป็น 7 เพราะ −

• วันที่ 1 เรากินแอปเปิ้ลที่ปลูกในวันแรก

• วันที่ 2 เรากินแอปเปิ้ลที่โตในวันที่สอง

• วันที่ 3 เรากินแอปเปิ้ลที่โตในวันที่สอง แต่หลังจากวันนี้ แอปเปิลที่ปลูกในวันที่สามจะเน่าเสีย

• ในวันที่ 4 ถึง 7 เรากินแอปเปิ้ลที่โตในวันที่สี่

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• minheap :=กองว่างใหม่
• วัน :=0, res :=0
• สำหรับฉันในช่วง 0 ถึงขนาดของแอปเปิ้ล - 1 ทำ
  • วัน :=ฉัน
  • ในขณะที่ minheap ไม่ว่างเปล่าและค่า rot ของค่าสูงสุดของ minheap − วัน do
    • ลบองค์ประกอบด้านบนออกจาก minheap
  • nbrApple :=apples[i]
  • หมดอายุ :=i + วัน[i]-1
  • ถ้า nbrApple> 0 แล้ว
    • ใส่ (หมดอายุ, nbrApple) จับคู่ใน minheap
  • ถ้า minheap ไม่ว่างก็
    • (date, apple) :=องค์ประกอบบนสุดของ minheap และนำออกจาก heap
    • res :=res + 1
    • ถ้าแอปเปิ้ล> 1 แล้ว
      • ใส่ (วันที่, apple-1) จับคู่ใน minheap
• ในขณะที่ minheap ไม่ว่าง ทำ
  • วัน :=วัน + 1
  • ในขณะที่ minheap ไม่ว่างเปล่าและค่าเน่าของ minheap <วัน do
    • ลบองค์ประกอบด้านบนออกจาก minheap
  • ถ้า minheap ว่างแล้ว
    • ออกมาจากลูป
  • (date, apple) :=ด้านบนของ minheap และลบออกจาก heap
  • res :=res + 1
  • ถ้าแอปเปิ้ล> 1 แล้ว
    • ใส่ (วันที่, apple-1) จับคู่ใน minheap
• ผลตอบแทน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

7