Chương trình tìm giới hạn tối thiểu số quả bóng trong túi trong Python

Cho mảng nums với nums[i] là số quả bóng trong túi thứ i. Cho thêm giá trị mx — số phép chia tối đa. Mỗi phép chia: chọn một túi, tách thành hai túi mới (mỗi túi ít nhất 1 quả). "Phạt" (penalty) là số quả bóng lớn nhất trong một túi sau các phép chia. Mục tiêu: tối thiểu hóa penalty.

Ví dụ: nums = [4,8,16,4], mx = 4 → kết quả 4. Các bước: [4,8,16,4] → tách 16 → [4,8,8,8,4] → tách các 8 → [4,4,4,4,4,4,4,4]. Penalty = 4.

Giải thuật (Tìm kiếm nhị phân)

1. Hàm helper(target, mx): trả về True nếu có thể đạt penalty ≤ target với ≤ mx phép chia.
   • Nếu target == 0: trả về mx + 1.
   • Đếm tổng số phép chia cần: sum((num - 1) // target for num in nums).
   • Trả về count <= mx.
2. Chương trình chính:
   • left := max(sum(nums) // (len(nums) + mx), 1).
   • right := max(nums).
   • Trong khi left < right:
     • mid := (left + right) // 2.
     • Nếu helper(mid, mx): right := mid.
     • Ngược lại: left := mid + 1.
   • Trả về left.

Ví dụ minh họa

def helper(target, mx):
    if target == 0:
        return mx + 1
    count = 0
    for num in nums:
        count += (num - 1) // target
    return count <= mx

def solve(nums, mx):
    left, right = max(sum(nums) // (len(nums) + mx), 1), max(nums)
    while left < right:
        mid = (left + right) // 2
        if helper(mid, mx):
            right = mid
        else:
            left = mid + 1
    return left

nums = [4,8,16,4]
mx = 4
print(solve(nums, mx))

Đầu vào

[4,8,16,4], 4

Đầu ra

4