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

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def check(x):
            state = [False] * len(bloomDay)
            for i in range(len(bloomDay)):
                if bloomDay[i]-x<=0:
                    state[i] = True
            # print(state)
            ans,ii,k_test = 0,0,0
            # 以下两个while循环嵌套，会超时，目标是用一个循环解决。
            # while ii<len(state):
            #     while ii<len(state) and state[ii]==True:
            #         k_test += 1
            #         ii += 1
            #         if k_test==k:
            #             ans += 1
            #             k_test = 0
            #     if ii<len(state) and state[ii]==False:
            #         ii += 1
            #         k_test = 0
            # print(x,ans,ans >= m)
            # return ans >= m
            for ii in range(len(state)):
                if state[ii]==True:
                    k_test += 1
                    if k_test==k:
                        ans += 1
                        k_test = 0
                if state[ii]==False:
                    k_test = 0
            # print(x,ans,ans >= m)
            return ans >= m
        def search_II(check):   # 二分法找最小等待天数
            if len(bloomDay)<m*k:
                print("全部开花也无法满足")
                return -1
            left = 1
            right = max(bloomDay)
            while left<=right:
                mid = (left+right)>>1
                if check(mid):
                    right = mid-1
                else:
                    left = mid+1
            return left 
        return search_II(check)