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

更新于： 2020年12月2日

91 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告