【leetcode】1482. 制作 m 束花所需的最少天数（minimum-number-of-days-to-make-m-bouquets）（二分）[中等]

链接

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

耗时

解题：7 h 36 min
题解：16 min

题意

给你一个整数数组 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 中的最小值，最大的可能天数是 bloomDay 中的最大值。

对于某一个可能的天数，验证其是否满足能得到 m 束花。遍历 bloomDay 数组，如果验证的天数大于等于当前元素，说明在这个天数时，这朵花已经盛开。记录连续的盛开的花的子数组的长度，计算这个连续子数组可以得到多少束花。最后统计整个数组一共可以得到多少束花，如果得到的花束大于等于 m，则说明当前验证的天数可行。

时间复杂度： O ( n ∗ l o g ( m a x _ n u m − m i n _ n u m ) ) O(n*log(max\_num-min\_num)) O(n∗log(max_num−min_num))

AC代码

class Solution {
private:
    vector<int> bloomDay;
    int m, k;
public:
    bool check(int curr_day) {
        int bouquet = 0;
        int seq = 0;
        for(auto d : bloomDay) {
            if(curr_day >= d) {
                seq++;
            }
            else {
                bouquet += seq/k;
                seq = 0;
            }
        }
        bouquet += seq/k;
        return bouquet >= m;
    }
    int minDays(vector<int>& bloomDay, int m, int k) {
        this->bloomDay = bloomDay;
        this->m = m;
        this->k = k;
        
        int n = bloomDay.size();
        if(n < m*k) return -1;
        if(n == m*k) return *max_element(bloomDay.begin(), bloomDay.end());
        
        int s = *min_element(bloomDay.begin(), bloomDay.end());
        int t = *max_element(bloomDay.begin(), bloomDay.end());
        while(s < t) {
            int m = (s + ((t-s)>>1));
            if(check(m)) t = m;
            else s = m+1;
        }
        return s;
    }
};