길이가 n인 일과 사과라는 두 개의 배열이 있다고 가정합니다. n일 연속으로 매일 사과가 자라는 특별한 종류의 사과나무가 있습니다. i 번째 날에는 사과[i] 수만큼 자라서 일[i]일 후에 썩을 것이기 때문에 i+일[i]일에는 사과가 썩어서 먹을 수 없다고 말할 수 있습니다. 어떤 날. apples[i] =0이고 days[i] =0이면 i일에 사과 나무가 사과를 재배하고 있지 않음을 나타냅니다. 우리는 하루에 최대 1개의 사과를 섭취할 수 있습니다. (처음 n일이 지나도 계속 먹을 수 있습니다.) 여기서 우리는 우리가 먹을 수 있는 최대 사과 수를 찾아야 합니다.
따라서 입력이 apple =[1,2,3,5,2] days =[3,2,1,4,2]와 같으면 출력은 −
이기 때문에 7이 됩니다.-
첫째 날에는 첫째 날에 자란 사과를 먹습니다.
-
둘째 날에는 둘째 날에 자란 사과를 먹습니다.
-
셋째 날에는 둘째 날에 자란 사과를 먹습니다. 그러나 이 날이 지나면 사흘째에 자란 사과는 썩습니다.
-
4일부터 7일까지는 4일차에 자란 사과를 먹습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- minheap :=새로운 빈 힙
- 일 :=0, 해상도 :=0
- i 범위 0에서 사과 크기 - 1, do
- 요일 :=나
- minheap이 비어 있지 않고 minheap 상단의 값이 썩는 동안 - day, do
- 최상위 요소를 minheap에서 제거
- nbrApple :=사과[i]
- 만료:=i + 일[i]-1
- nbrApple> 0이면
- (만료, nbrApple) 쌍을 minheap에 삽입
- minheap이 비어 있지 않으면
- (date, apple) :=minheap의 최상위 요소 및 힙에서 제거
- res :=res + 1
- 사과가 1이면
- (날짜, 사과-1) 쌍을 minheap에 삽입
- minheap이 비어 있지 않은 동안 do
- 일 :=일 + 1
- minheap이 비어 있지 않고 minheap 상단의 값이 썩는 동안
- 최상위 요소를 minheap에서 제거
- minheap이 비어 있으면
- 루프에서 나오다
- (date, apple) :=minheap의 맨 위 및 힙에서 제거
- res :=res + 1
- 사과가 1이면
- (날짜, 사과-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