Python程式：查詢跳傘者在k天內所需的最小飛機空間

假設我們有一個名為 nums 的數字列表，其中每個值代表一組希望一起跳傘的人。我們還有另一個值 k，表示他們可以申請跳傘的天數。我們必須找到我們需要能夠在 k 天內滿足所有請求的飛機的最小容量。請求應按其給定的順序滿足，並且飛機每天只能飛行一次。

因此，如果輸入類似於 nums = [16, 12, 18, 11, 13]，k = 3，則輸出將為 28，因為 28 人座的飛機可以將給定的請求分組為 [16, 12]、[18]、[11, 13]。

為了解決這個問題，我們將遵循以下步驟：

• 如果 nums 為空，則
  • 返回 0
• start := nums 的最大值，end := nums 所有元素的總和
• 當 start < end 時，執行以下操作：
  • mid := (start + end) / 2
  • days := 1，temp := 0
  • 對於 nums 中的每個 num，執行以下操作：
    • 如果 temp + num > mid，則
      • days := days + 1
      • temp := num
    • 否則，
      • temp := temp + num
  • 如果 days > k，則
    • start := mid + 1
  • 否則，
    • end := mid
• 返回 start

讓我們看看以下實現以更好地理解：

示例

線上演示

class Solution:
   def solve(self, nums, k):
      if not nums:
         return 0

      start, end = max(nums), sum(nums)

      while start < end:
         mid = (start + end) // 2

         days = 1
         temp = 0
         for num in nums:
            if temp + num > mid:
               days += 1
               temp = num
            else:
               temp += num

         if days > k:
            start = mid + 1
         else:
            end = mid

      return start

ob = Solution()
nums = [16, 12, 18, 11, 13]
k = 3
print(ob.solve(nums, k))

輸入

[16, 12, 18, 11, 13], 3

輸出

28

Arnab Chakraborty

更新於： 2020年12月2日

91 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習