LeetCode1482(2021.5.9)

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

class Solution {
public:
    int n, m, k;
    int inf = 0x3f3f3f3f;

    bool ck(vector<int> nums, int mid){
        int cnt = 0;
        for(int i = 0; i < n && cnt < m;){
            int cur = nums[i] <= mid ? 1 : 0;
            int j = i;
            if(cur){
                while(cur < k && j + 1 < n && nums[j + 1] <= mid) j++, cur++;
                if(cur == k) cnt++;
                i = j + 1;
            }
            else i++;
        }
        return cnt >= m;
    }

    int minDays(vector<int>& bloomDay, int t_m, int t_k) {
        m = t_m, k = t_k;
        n = bloomDay.size();
        if(n < m * k) return -1;
        int l = 0, r = inf;
        while(l < r){
            int mid = l + r >> 1;
            if(ck(bloomDay, mid)) r = mid;
            else l = mid + 1;
        }
        return ck(bloomDay, l) ? l : -1;
    }
};

发表评论