LeetCode每日一题：制作 m 束花所需的最少天数

传送门

思路

题目是很标准的“找到最大或最小”，也就是说假设正解为ans，(-∞,ans)范围内都无法满足题设条件，而[ans,+∞)都能满足要求，且ans是满足要求的值中最小的那个，这样ans就是一个“合法与非法”的分割点。对于形如这样的题设，就可以对答案序列进行二分来在一个较优的复杂度内枚举到答案。

就本体内容具体地看，天数显然就是我们二分的目标。枚举的左边界是0，右边界是bloomDay中最大值，这是显然地。

每次获取一个mid，然后去检查这个天数mid能否满足要求。如果可以的话，说明mid落在了[ans,+∞)范围内，令r=mid，继续；

如果不可以满足要求，那么说明mid落在了(-∞,ans) 范围内，令l=mid+1，缩小范围继续查找。

值得一提的是，与传统的二分不同，我们在缩小右边界时并非是r=mid-1，这是因为答案区间[ans,+∞)是左闭右开的，是可能存在r==ans的，如果这时还去-1，就会导致答案错误。

代码

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

        vector<bool> flag(n);
        int l = 0, r = *max_element(bloomDay.begin(), bloomDay.end());
        while(l < r) {
            int mid = (l + r) / 2;
            if (check(bloomDay, mid, flag, m, k)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        // 如果二分终点值r都不合法，就找不到合法答案
        return check(bloomDay, r, flag, m, k) ? r : -1;
    }

    bool check(vector<int>& bld, int mid, vector<bool>& f, int m, int k) {
        int n = bld.size();

        // 初始化flag数组
        // 标记已经盛开的花朵
        for (int i = 0; i < n; i++) {
            f[i] = bld[i] <= mid;
        }

        // O(n)枚举
        int cnt = 0;
        for (int i = 0; i < n && cnt < m; ) {
            // 如果花朵i已经盛开
            if (f[i]) {
                int cur = 1, j = i;
                // 去枚举相邻的k朵花是不是也盛开了
                while (cur < k && j + 1 < n && f[j + 1]) {
                    j++;
                    cur++;
                }
                // 如果都盛开了，计数++
                if (cur == k) cnt++;
                // 从这相邻的一组花再后一个位置继续枚举
                i = j + 1;
            } else {
                // 如果没开就直接跳
                i++;
            }
        }

        return cnt >= m;
    }
};