Re: [閒聊] 每日leetcode已回收
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;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.53.5 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718761338.A.3C3.html
推
06/19 09:43,
1年前
, 1F
06/19 09:43, 1F
推
06/19 15:51,
1年前
, 2F
06/19 15:51, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 381 之 1550 篇)：