1482. Minimum Number of Days to Make m Bouquets
You are given an integer array bloomDay, an integer m and an integer k.
You want to make m bouquets. To make a bouquet, you need to use k adjacent flowe
rs from the garden.
The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] a
nd 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 = 1
Output: 3
题目 :
花园里面有花
在他们的 bloomDay[i] 天开花
如果想要有m群 有k个相邻的花 的花丛
那么最少需要几天
思路 :
想了一阵子的heap dp
heap要记录index 然后把花连起来的话
会非常麻烦 而且会有很多例外
dp会超时
偷看一下提示 二分搜
用天数来二分搜就可以了
姆咪
```cpp
class Solution {
public:
bool find(vector<int>& bloomDay, int m, int k , int d)
{
int len = bloomDay.size();
int now = 0;
int all = 0;
for(int i = 0 ; i < len ; i ++)
{
if(d >= bloomDay[i])now ++;
else now = 0;
if(now >= k)
{
all ++;
now = 0;
}
}
if(all >= m)return 1;
else return 0;
}
int minDays(vector<int>& bloomDay, int m, int k)
{
int len = bloomDay.size();
if( (long long)m * (long long)k > len )return -1;
int r = 0;
int l = 0;
for(int hi : bloomDay)
{
r = max(r,hi);
}
while(l<r)
{
int d = (l+r)/2;
bool dn = find(bloomDay,m,k,d) ;
if(dn)
{
r = d ;
}
else
{
l = d +1;
}
}
return l;
}
};
```