โปรแกรมหาขีดจำกัดล่างของจำนวนลูกบอลในถุงน้อยที่สุดใน Python

ปัญหา

มีอาร์เรย์ nums โดย nums[i] คือจำนวนลูกบอลในถุงที่ i และมีค่า mx เป็นจำนวนครั้งสูงสุดที่สามารถแบ่งถุงได้ การดำเนินการคือเลือกถุงหนึ่งแบ่งเป็นสองถุงใหม่ที่มีลูกบอลอย่างน้อย 1 ลูก ค่าปรับ (penalty) คือจำนวนลูกบอลสูงสุดในถุงใดถุงหนึ่ง ต้องการลดค่าปรับให้น้อยที่สุดหลังดำเนินการได้สูงสุด mx ครั้ง

ตัวอย่าง

nums = [4,8,16,4], mx = 4 → ผลลัพธ์คือ 4 เพราะแบ่งถุง 16 เป็น 8,8 แล้วแบ่ง 8 แต่ละอันเป็น 4,4 จนได้ถุงทั้งหมดเป็น 4 ลูกบอล

ขั้นตอนการแก้ปัญหา

1. กำหนดฟังก์ชันช่วย helper(target, mx):
   • ถ้า target == 0 คืน mx + 1
   • count := 0
   • สำหรับแต่ละ num ใน nums: count += (num - 1) // target
   • คืน count <= mx
2. จากเมธอดหลัก:
   • left := max(sum(nums) // (len(nums) + mx), 1)
   • right := max(nums)
   • بينما left < right:
     • mid := (left + right) // 2
     • ถ้า helper(mid, mx) จริง: right := mid
     • มิฉะนั้น: left := mid + 1
   • คืน left

การนำไปใช้งาน (Python)

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

อินพุต

[4,8,16,4], 4

เอาต์พุต

4