Chương trình tìm máy bay không gian tối thiểu cần thiết cho người nhảy dù trong k ngày trong python

Giả sử chúng ta có một danh sách các số được gọi là num trong đó mỗi giá trị đại diện cho một nhóm người đang tìm cách nhảy dù cùng nhau. Và chúng tôi có một giá trị k khác đại diện cho số ngày họ có thể đăng ký nhảy dù. Chúng tôi phải tìm ra sức chứa tối thiểu của chiếc máy bay mà chúng tôi cần để có thể đáp ứng mọi yêu cầu trong vòng k ngày. Các yêu cầu phải được thực hiện theo thứ tự mà chúng đã được đưa ra và máy bay chỉ có thể bay một lần mỗi ngày.

Vì vậy, nếu đầu vào là nums =[16, 12, 18, 11, 13], k =3, thì đầu ra sẽ là 28, vì máy bay 28 người có thể nhóm các yêu cầu đã cho theo [16, 12], [ 18], [11, 13].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu nums trống, thì
  • trả về 0
• start:=tối đa nums, end:=tổng tất cả các phần tử của nums
• trong khi bắt đầu
• giữa:=(bắt đầu + kết thúc) / 2
• ngày:=1, tạm thời:=0
• đối với mỗi num trong nums, thực hiện
  • if temp + num> mid, then
    • ngày:=ngày + 1
    • temp:=num
  • nếu không,
    • temp:=temp + num
• nếu ngày> k, thì
  • start:=mid + 1
• nếu không,
  • end:=mid

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

28