Chương trình tìm số tàu vũ trụ tối thiểu để cứu hộ bằng Python

Cho danh sách weights thể hiện cân nặng mọi người và giới hạn limit của một tàu vũ trụ. Mỗi tàu chở tối đa 2 người. Tìm số tàu tối thiểu để cứu tất cả mọi người.

Ví dụ: weights = [300, 400, 300], limit = 600 → 2 (một tàu chở hai người 300, một tàu chở người 400).

Quy trình giải quyết

1. Sắp xếp weights.
2. Khởi tạo cnt = 0.
3. Trong khi weights không rỗng:
   • Lấy phần tử lớn nhất x = weights.pop().
   • Nếu weights không rỗng và weights[0] <= limit - x, loại bỏ phần tử nhỏ nhất weights.pop(0).
   • cnt += 1.
4. Trả về cnt.

Ví dụ mã nguồn

class Solution:
    def solve(self, weights, limit):
        weights.sort()
        cnt = 0
        while weights:
            x = weights.pop()
            if weights and weights[0] <= limit - x:
                weights.pop(0)
            cnt += 1
        return cnt

ob = Solution()
weights = [300, 400, 300]
limit = 600
print(ob.solve(weights, limit))  # Output: 2

Đầu vào

[300, 400, 300], 600

Đầu ra

2