Pythonでk日以内にスカイダイバーに必要な最小スペースプレーンを見つけるプログラム

numsと呼ばれる数値のリストがあり、各値は一緒にスカイダイビングをしようとしている人々のグループを表しているとします。また、スカイダイビングに適用できる日数を表す別の値kがあります。 k日以内にすべての要求を満たすことができるようにするために必要な飛行機の最小容量を見つける必要があります。リクエストは指定された順序で実行する必要があり、飛行機は1日1回しか飛行できません。

したがって、入力がnums =[16、12、18、11、13]、k =3の場合、28人の飛行機が[16、12]、[で指定された要求をグループ化できるため、出力は28になります。 18]、[11、13]。

これを解決するには、次の手順に従います-

• numsが空の場合、
  • 0を返す
• start：=numsの最大値、end：=numsのすべての要素の合計
• 開始<終了中、実行
  • mid：=（開始+終了）/ 2
  • 日：=1、臨時雇用者：=0
  • numsの各numについて、実行します
    • temp + num> midの場合、
      • 日数：=日数+ 1
      • temp：=num
    • それ以外の場合、
      • temp：=temp + num
  • 日数>kの場合、
    • start：=mid + 1
  • それ以外の場合、
    • end：=mid
• リターンスタート

理解を深めるために、次の実装を見てみましょう-

例

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