Chương trình Python tìm độ dài lớn nhất của k dải băng cùng độ dài

Cho danh sách độ dài dải băng ribbons và số k. Có thể cắt dải băng thành nhiều đoạn nhỏ hơn. Tìm độ dài r lớn nhất sao cho có thể tạo được ít nhất k dải băng độ dài r. Trả về -1 nếu không thể.

Ví dụ

Input: ribbons = [1, 2, 5, 7, 15], k = 5

Output: 5

Giải thích: 15 → 3×5, 7 → 5+2, có sẵn 5 → tổng 5 dải độ dài 5.

Thuật toán (Binary Search)

1. Khoảng tìm: left = 0, right = max(ribbons).
2. Khi left < right:
   • mid = (left + right + 1) // 2 (upper mid tránh lặp vô tận).
   • Tính tổng số dải độ dài mid có được: sum(ribbon // mid for ribbon in ribbons).
   • Nếu ≥ k → left = mid (thử độ dài lớn hơn).
   • Ngược lại → right = mid - 1.
3. Nếu left > 0 trả về left, else -1.

Mã nguồn Python

def solve(ribbons, k):
    left, right = 0, max(ribbons)
    while left < right:
        mid = (left + right + 1) // 2
        if sum(ribbon // mid for ribbon in ribbons) >= k:
            left = mid
        else:
            right = mid - 1
    return left if left else -1

# Test
ribbons = [1, 2, 5, 7, 15]
k = 5
print(solve(ribbons, k))  # Output: 5

Độ phức tạp

• Thời gian: O(n log M), M = max(ribbons).
• Không gian: O(1).