使用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.