1482. Minimum Number of Days to Make m Bouquets (python+cpp)

题目

解法：二分判定

这道题关键在于想到用二分判定去做。因为假设m天能够成功的话，那么大于m的天数一定也是可以的。反过来说，m天不可以，那么小于m的天数一定都不可以，这样子其实我们只需要去找False和True的分界线即可。
关于每次判定，相当于从一个固定的序列判断是否成功，很简单的O(n)就可以做。所以总体复杂度是O(nlogn)

python版本

class Solution:def minDays(self, bloomDay: List[int], m: int, k: int) -> int:def check(day):arr = [1 if x<=day else 0 for x in bloomDay]formed = 0tmp = 0for num in arr:if num:tmp += 1if tmp==k:formed += 1tmp = 0else:tmp = 0return formed>=mlo = min(bloomDay)hi = max(bloomDay)+1while lo+1<hi:mid = lo + (hi-lo)//2if check(mid):hi = midelse:lo = midif check(lo):return loelse:if hi==max(bloomDay)+1:return -1else:return hi

C++版本

class Solution {
    
public:int minDays(vector<int>& bloomDay, int m, int k) {
    int lo = *min_element(bloomDay.begin(),bloomDay.end()), hi = *max_element(bloomDay.begin(),bloomDay.end())+1, mid;while (lo+1<hi){
    mid = lo + (hi-lo)/2;if (check(bloomDay,m,k,mid)){
    hi = mid;}else{
    lo = mid;}}if (check(bloomDay,m,k,lo)){
    return lo;}else{
    if (hi==*max_element(bloomDay.begin(),bloomDay.end())+1){
    return -1;}else{
    return hi;}}}bool check(vector<int>& bloomDay, int m, int k, int mid){
    vector<int> arr(bloomDay.size(),0);for (int i=0;i<bloomDay.size();i++){
    if (bloomDay[i]<=mid) arr[i] = 1;}int formed = 0, tmp = 0;for (auto num:arr){
    if (num>0){
    tmp += 1;if (tmp==k){
    formed += 1;tmp = 0;}}else{
    tmp = 0;}}return formed>=m;}
};