動機
- 只要有某個範圍是連續遞增就可以用bsearch!!
- 寫bsearch就是考慮那邊要丟掉就設成
a = mid+1
Problem
Given an integer array bloomDay
, an integer m
and an integer k
.
We need to make m
bouquets. To make a bouquet, you need to use k
adjacent flowers from the garden.
The garden consists of n
flowers, the ith
flower will bloom in the bloomDay[i]
and then can be used in exactly one bouquet.
Return the minimum number of days you need to wait to be able to make m
bouquets from the garden. If it is impossible to make m
bouquets return -1.
Example 1:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1Output: 3Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.We need 3 bouquets each should contain 1 flower.After day 1: [x, _, _, _, _] // we can only make one bouquet.After day 2: [x, _, _, _, x] // we can only make two bouquets.After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.
Example 2:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2Output: -1Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.
Example 3:
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3Output: 12Explanation: We need 2 bouquets each should have 3 flowers.Here's the garden after the 7 and 12 days:After day 7: [x, x, x, x, _, x, x]We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.After day 12: [x, x, x, x, x, x, x]It is obvious that we can make two bouquets in different ways.
Example 4:
Input: bloomDay = [1000000000,1000000000], m = 1, k = 1Output: 1000000000Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.
Example 5:
Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2Output: 9
Constraints:
bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n
Sol
class Solution:
def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
if m*k > len(bloomDay):
return -1
def count(day):
ret = 0
i = 0
while i < len(bloomDay):
if bloomDay[i] <= day:
j = i+1
while j < len(bloomDay) and bloomDay[j] <= day:
j += 1
ret += (j-i)//k
i = j
else:
i += 1
return ret
a,b = min(bloomDay), max(bloomDay)
while a<b:
mid = (a+b)//2
#print(a,mid,b,count(mid))
if count(mid) < m:
a = mid+1
else:
b = mid
return a