力扣1482.制作m束花所需的最少时间
力扣1482.制作m束花所需的最少时间
-
二分答案
- check的时候
- 用一个bool数组判断是否开花
- 找连续的k朵花
- check的时候
-
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;}};