Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

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
推 SecondRun: 別卷了
推 orangeNoob: 看不懂跟二分搜尋有什麼關係 :(