使用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 := bloomDay 的大小

  • 如果 m * k > n，则

    • 返回 -1

  • 定义一个函数 possible()。这将采用 x

  • count := 0, bouquets := 0

  • 对于 bloomDay 中的每个 d，执行：

    • 如果 d <= x，则

      • count := count + 1

      • 如果 count 等于 k，则

        • bouquets := bouquets + 1

        • count := 0

    • 否则，

      • count := 0

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

  • 从主方法执行以下操作：

  • left := 0, right := 1 + bloomDay 的最大值

  • 当 left < right 时，执行：

    • mid := (left + right) / 2

    • 如果 possible(mid) 为 true，则

      • right := mid

    • 否则，

      • left := mid + 1

  • 如果 possible(left) 为 true，则

    • 返回 left

  • 否则返回 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

更新于：2021年5月29日

637 次浏览

启动您的职业生涯

完成课程后获得认证

开始
广告
© . All rights reserved.