使用 Python 查找制作 m 束花的最少天数的程序

假设我们有一个名为 nums 的整数数组，我们还有另外两个值 m 和 k。现在，我们需要制作 m 个花束。要制作一束花，我们需要花园中的 k 朵相邻的花。这里的花园由n种不同的花组成，第i朵花将在bloomDay[i]盛开。每朵花只能用在一个花束中。我们必须找到从花园里制作 m 束花需要等待的最少天数。如果我们不能制作 m 个花束，则返回 -1。

所以，如果输入是像bloomDay = [5,5,5,5,10,5,5] m = 2 k = 3，那么输出将是10，因为我们需要2 (m = 2)个花束，每个应该有3朵花。

• 第 5 天后：[x, x, x, x, _, x, x]，我们可以用前三朵开花的花制作一束花，但不能制作另一束花

• 第 10 天后：[x, x, x, x, x, x, x]，现在我们可以用不同的方法制作两束花束了。

为了解决这个问题，我们将按照以下步骤操作 -

• n := 开花日的大小

• 如果 m * k > n，则

• 返回-1

• 定义一个函数possible()。这将需要 x

• 计数：= 0，花束：= 0

• 对于每个 d 花开日，做

• 计数：= 0

• 计数 := 计数 + 1

• 如果计数与 k 相同，则

• 花束 := 花束 + 1

• 计数：= 0

• 如果 d <= x，则

• 否则，

• 如果花束 >= m，则返回 true，否则返回 false

• 从主要方法执行以下操作 -

• 左：= 0，右：= 1 + 最大的bloomDay

• 当左 < 右时，做

• 左 := 中 + 1

• 右 := 中

• 中：=（左+右）/2

• 如果possible(mid)是真的，那么

• 否则，

• 如果possible(left)是真的，那么

• 返回左

• 否则返回左 + 1

让我们看看以下实现以获得更好的理解 -

示例

def solve(bloomDay, m, k):
   n = len(bloomDay)
   if m * k > n:
      return -1
   def possible(x):
      count = 0
      bouquets = 0
      for d in bloomDay:
         if d <= x:
            count += 1
            if count == k:
               bouquets += 1
               count = 0
         else:
            count = 0
      return bouquets >= m
   left, right = 0, max(bloomDay) + 1
   while left < right:
      mid = (left + right)//2
      if possible(mid):
         right = mid
      else:
         left = mid + 1
   if possible(left):
      return left
   else:
      return left + 1
bloomDay = [5,5,5,5,10,5,5]
m = 2
k = 3
print(solve(bloomDay, m, k))

输入

[5,5,5,5,10,5,5], 2, 3

10