Chương trình tìm dung lượng máy bay tối thiểu cho nhảy dù trong k ngày bằng Python

Cho danh sách nums (kích thước nhóm nhảy dù) và số ngày k. Máy bay chỉ bay 1 lần/ngày, phải phục vụ nhóm theo thứ tự. Tìm dung lượng tối thiểu của máy bay để phục vụ hết trong k ngày.

Ví dụ: nums=[16,12,18,11,13], k=3 → 28 (nhóm [16,12], [18], [11,13]).

Giải thuật

• Tìm kiếm nhị phân dung lượng trong khoảng [max(nums), sum(nums)].
• Với dung lượng mid, tính số ngày cần: gom nhóm liên tiếp miễn là tổng ≤ mid.
• Nếu ngày > k → tăng dung lượng; ngược lại giảm.

Ví dụ minh họa

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