# LeetCode 1482. Minimum Number of Days to Make m Bouquets

https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/description/

## 題目大意

做一束花束需要從花園拿連續 `k` 朵花，目標是做 `m` 束花束

`bloomDay` 是每朵花在第幾天綻放

問最少要等幾天才能完成目標？辦不到回傳 `-1`

## 思考

對於**等待的天數**，它是有個範圍的，也就是 `bloomDay` 裡最早開花的是下界、最晚開花是上界

而我們先不看實際花什麼時候開花，就會發現在這段可能的等待日子裡，日子顯然是有序的連續數字

所以我們可以對這段日子使用 binary search ，每次都猜中間的日子，之後只要檢驗能不能做出 `m` 束花束即可

class Solution
{
public:
    int minDays(vector<int> &bloomDay, int m, int k)
    {
        if (bloomDay.size() < static_cast<long>(m) * k)
            return -1;

        const auto minmax = minmax_element(bloomDay.begin(), bloomDay.end());
        int l = *(minmax.first), r = *(minmax.second);

        while (l < r)
        {
            const int mid = (l + r) / 2;
            if (bouquetsMade(bloomDay, k, mid) < m)
                l = mid + 1;
            else
                r = mid;
        }

        return l;
    }

private:
    int bouquetsMade(const vector<int> &bloomDay, int k, int waiting)
    {
        int cnt = 0, cur = 0;

        for (const int day : bloomDay)
        {
            if (day > waiting)
                cur = 0;
            else if (++cur == k)
            {
                ++cnt;
                cur = 0;
            }
        }

        return cnt;
    }
};