力扣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; } };