力扣1482.制作m束花所需的最少时间

力扣1482.制作m束花所需的最少时间

• 二分答案

  • check的时候
    • 用一个bool数组判断是否开花
    • 找连续的k朵花

•   const int N = 1e5+10;
    int st[N];
    class Solution {
    public:
        int minDays(vector<int>& bloomDay, int m, int k) {
            int n = bloomDay.size();
            if(n < (long long)m*k) return -1;
            auto check = [&](int mid) -> bool
            {
                for(int i=0;i<n;i++)
                    st[i] = bloomDay[i] <= mid;
                int cnt=0;  //记录已制作多少花
                for(int i=0;i<n&&cnt<m;i++)
                {
                    if(st[i])
                    {
                        //记录当前连续的花的数量
                        int cur = 1;
                        while(cur<k && i<n-1 && st[i+1])
                        {
                            i ++;
                            cur++;
                        }
                        if(cur == k) cnt++;
                    }
                }
                return cnt>=m;
            };
            int l = 0,r = (int)1e9;
            while(l<r)
            {
                int mid = l+r>>1;
                if(check(mid)) r = mid;
                else l = mid+1;
            }
            return check(r) ? r:-1;
        }
    };