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

题目如下

数据范围

示例

这道题和我写过的2226. 每个小孩最多能分到多少糖果一个思路先确定上下界然后使用二分查找。
做本题之前还要看花的数量够不够花束所需要的花的数。
本题的上界就是最晚开的花因为过了这个时间也不会有新的花开了，下界就是最早开的花很显然。
同样因为开花时间很大不能一个一个枚举只能通过二分查找来加速。

通过代码

class Solution {
public:
    bool check(vector<int>& ns, int m, int k, int day) {
        int l = 0, n = ns.size();
        int count = 0, c = 0;
        for (int i = 0; i < n; i++) {
            if (ns[i] <= day) {
                c++;
                if(c == k){
                count += 1;
                c = 0;
            }
            } else
                c = 0;
        }
        return count >= m;
    }
    int minDays(vector<int>& bloomDay, int m, int k) {
        int n = bloomDay.size(), mid;
        int l = *min_element(bloomDay.begin(), bloomDay.end());
        int r = *max_element(bloomDay.begin(), bloomDay.end());
        if (n /k < m)
            return -1;
        while (l < r) {
            mid = l + (r - l) / 2;
            if (check(bloomDay, m, k, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};