สมมติว่าเรามีอาร์เรย์สองอาร์เรย์ชื่อ days และ apples ความยาวเท่ากัน n มีต้นแอปเปิลพิเศษที่ออกแอปเปิลทุกวันเป็นเวลา n วันติดต่อกัน ในวันที่ i ต้นไม้ออกแอปเปิล apples[i] ลูก และจะเน่าหลังจาก days[i] วัน กล่าวคือ ในวันที่ i + days[i] แอปเปิลจะเน่าและกินไม่ได้ ในบางวัน หาก apples[i] = 0 และ days[i] = 0 แสดงว่าในวันที่ i ต้นไม้ไม่ออกแอปเปิล เราสามารถกินได้สูงสุดหนึ่งลูกต่อวัน (สามารถกินต่อได้หลังจาก n วันแรก) เราต้องหาจำนวนแอปเปิลสูงสุดที่เราสามารถกินได้
เช่น ถ้าอินพุตคือ apples = [1,2,3,5,2] days = [3,2,1,4,2] ผลลัพธ์จะเป็น 7 เพราะ:
- วันที่ 1 กินแอปเปิลที่ออกในวันแรก
- วันที่ 2 กินแอปเปิลที่ออกในวันที่สอง
- วันที่ 3 กินแอปเปิลที่ออกในวันที่สอง อีกครั้ง หลังวันนี้ แอปเปิลวันที่สามจะเน่า
- วันที่ 4 ถึง 7 กินแอปเปิลที่ออกในวันที่สี่
วิธีแก้ปัญหา
- minheap := heap ใหม่ว่างเปล่า
- day := 0, res := 0
- สำหรับ i ในช่วง 0 ถึงขนาดของ apples - 1:
- day := i
- while minheap ไม่ว่าง และค่าเน่าของ top ของ minheap < day: ลบ top ออกจาก minheap
- nbrApple := apples[i]
- expiration := i + days[i] - 1
- ถ้า nbrApple > 0: แทรก (expiration, nbrApple) ลง minheap
- ถ้า minheap ไม่ว่าง:
- (date, apple) := top ของ minheap และลบออกจาก heap
- res := res + 1
- ถ้า apple > 1: แทรก (date, apple-1) ลง minheap
- while minheap ไม่ว่าง:
- day := day + 1
- while minheap ไม่ว่าง และค่าเน่าของ top < day: ลบ top ออกจาก minheap
- ถ้า minheap ว่าง: ออกจากลูป
- (date, apple) := top ของ minheap และลบออกจาก heap
- res := res + 1
- ถ้า apple > 1: แทรก (date, apple-1) ลง minheap
- return res
ตัวอย่าง
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
