nums라는 정수가 있는 배열이 있고 또 다른 두 개의 값 m과 k가 있다고 가정합니다. 이제 m개의 꽃다발을 만들어야 합니다. 하나의 꽃다발을 만들려면 정원에서 k 개의 인접한 꽃이 필요합니다. 여기 정원은 n개의 다른 꽃으로 구성되어 있으며, i번째 꽃은 bloomDay[i]에 피어납니다. 각 꽃은 하나의 부케에만 사용할 수 있습니다. 우리는 정원에서 m개의 꽃다발을 만들기 위해 기다려야 하는 최소 일수를 찾아야 합니다. m 부케를 만들 수 없으면 -1을 반환합니다.
따라서 입력이 bloomDay =[5,5,5,5,10,5,5] m =2 k =3과 같으면 출력은 10이 됩니다. 왜냐하면 우리는 2(m =2) 꽃다발이 필요하고 각각은 3개의 꽃이 있습니다.
-
5일차:[x, x, x, x, _, x, x] 이후에 처음 3개의 꽃으로 꽃다발을 만들 수 있지만 다른 꽃다발은 만들 수 없습니다.
-
10일차 이후:[x, x, x, x, x, x, x], 이제 서로 다른 방식으로 두 개의 꽃다발을 만들 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=bloomDay의 크기
-
m * k> n이면
-
반환 -1
-
-
가능한() 함수를 정의합니다. 시간이 걸립니다.
-
개수 :=0, 꽃다발 :=0
-
bloomDay의 각 d에 대해
-
d <=x이면
-
개수 :=개수 + 1
-
개수가 k와 같으면
-
꽃다발 :=꽃다발 + 1
-
개수 :=0
-
-
-
그렇지 않으면
-
개수 :=0
-
-
-
꽃다발이 m보다 크면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
-
주요 방법에서 다음을 수행하십시오 -
-
왼쪽 :=0, 오른쪽 :=1 + bloomDay의 최대값
-
왼쪽 <오른쪽, 하는 동안
-
중간 :=(왼쪽 + 오른쪽) /2
-
가능한(mid)이 참이면
-
오른쪽 :=중간
-
-
그렇지 않으면
-
왼쪽 :=중간 + 1
-
-
-
가능한(왼쪽)이 참이면
-
왼쪽으로 돌아가기
-
-
그렇지 않으면 왼쪽 + 1 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def solve(bloomDay, m, k): n = len(bloomDay) if m * k > n: return -1 def possible(x): count = 0 bouquets = 0 for d in bloomDay: if d <= x: count += 1 if count == k: bouquets += 1 count = 0 else: count = 0 return bouquets >= m left, right = 0, max(bloomDay) + 1 while left < right: mid = (left + right)//2 if possible(mid): right = mid else: left = mid + 1 if possible(left): return left else: return left + 1 bloomDay = [5,5,5,5,10,5,5] m = 2 k = 3 print(solve(bloomDay, m, k))
입력
[5,5,5,5,10,5,5], 2, 3
출력
10