一、题目

题目链接

1482. 制作 m 束花所需的最少天数.

题面

给你一个整数数组 bloomDay，以及两个整数 m 和 k 。

现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。

花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

数据范围

bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <=10^6
1 <= k <= n

样例

输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x表示花开，而 _ 表示花还未开。 现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _] // 只能制作 1 束花
2 天后：[x, _, _, _, x] // 只能制作 2 束花
3 天后：[x, _, x, _, x] // 可以制作 3 束花，答案为 3

输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。

输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵。 花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。

二、思路

看数据猜算法

n是1e5级别的，也就是 O(n logn) 的算法，又是找需要最小天数的“最优解”，可以想到二分法。

算法实现思路

用二分法寻找最优的天数。显然，假如 i 天能完成，那么 j 天（j>=i）天也能完成。
每次二分天数，需要一个 O(n) 级别的check函数，检查是否能实现。
每次check(day)，需要找的是连续的长度==k且bloomDay[i]<=day 的片段，那么可以这样实现。

bool check(int day)
    {
   
        int flowers=0,bouquets=0;
        for(int i=0;i<num.size();i++)
        {
   
            if(num[i]<=day)
            {
   
                flowers++;
                if(flowers==k)
                {
   
                    bouquets++;
                    flowers=0;
                }
            }
            else
            {
   
                flowers=0;
                
            }
        }
        if(bouquets>=m)return 1;
        else return 0;
    }

读到一个bloomDay[i]<=day，说明这枝花可以用，flowers++；
如果连续一段flowers的长度等于k，那么可以构成一个花束bouquet，bouquets++，flowers归零；
如果读到一个大于day的bloomDay[i]，说明前面的flowers已经不能构成一个花束，flowers也归零。

三、代码

• tips：注意ans初值为-1，如果找不到答案就会返回-1。

class Solution 
{
   
    vector<int> num;
    int tot,len;

    bool check(int day)
    {
   
        int flowers=0,bouquets=0;
        for(int i=0;i<num.size();i++)
        {
   
            if(num[i]<=day)
            {
   
                flowers++;
                if(flowers==len)
                {
   
                    bouquets++;
                    flowers=0;
                }
            }
            else
            {
   
                flowers=0;
            }
        }
        if(bouquets>=tot)return 1;
        else return 0;
    }

public:
    int minDays(vector<int>& bloomDay, int m, int k) 
    {
   
        num=bloomDay;
        tot=m;
        len=k;
        int l=0,r=1e9+7,ans=-1;
        while(l<=r)
        {
   
            int mid=(l+r)/2;
            if(check(mid))
            {
   
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        return ans;
    }
};