Python - หาขนาดสูงสุดสำหรับการตัดล็อกเพื่อจัดเก็บในฐานข้อมูล

โจทย์: กำหนดรายการขนาดล็อก logs และขีดจำกัด limit แต่ละ logs[i] คือขนาดล็อกของผู้ใช้ i ต้องการหา ค่า x สูงสุด ที่ถ้าตัดล็อกทุกตัวให้ไม่เกิน x ผลรวมขนาด ≤ limit หากไม่ต้องตัดเลย ให้คืนค่าล็อกสูงสุด

ตัวอย่าง

Input: logs = [500, 200, 10000, 500, 4000], limit = 3000
Output: 900
เหตุผล: ตัดที่ 900 ได้ [500, 200, 900, 500, 900] ผลรวม = 3000

อัลกอริทึม: Binary Search on Answer

ฟังก์ชัน f(x) = sum(min(x, log) for log in logs) เป็นฟังก์ชันไม่ลดลง (Monotonic) → ใช้ Binary Search หา x สูงสุดที่ f(x) ≤ limit

ขั้นตอนการทำงาน

1. lo = 0, hi = max(logs) + 1
2. วนลูป while lo + 1 < hi:
   • mi = lo + (hi - lo) // 2
   • คำนวณ total = sum(min(mi, log) for log in logs)
   • หาก total <= limit: lo = mi (ลองค่ามากขึ้น)
   • มิฉะนั้น: hi = mi (ลองค่าน้อยลง)
3. คืนค่า lo

โค้ด Python

def solve(logs, limit):
    lo, hi = 0, max(logs) + 1
    
    while lo + 1 < hi:
        mi = lo + (hi - lo) // 2
        if sum(min(mi, log) for log in logs) <= limit:
            lo = mi
        else:
            hi = mi
    
    return lo

# ทดสอบ
logs = [500, 200, 10000, 500, 4000]
limit = 3000
print(solve(logs, limit))  # Output: 900

การทำงานทีละขั้นตอน (Trace)

logs = [500, 200, 10000, 500, 4000], limit = 3000

จบลูป (lo+1=901 >= hi=901) → คืนค่า 900

ความซับซ้อน

• Time Complexity: O(n log M) โดย M = max(logs)
• Space Complexity: O(1)

กรณีพิเศษ

print(solve([100, 200, 300], 1000))  # 300 (ไม่ต้องตัด ผลรวม 600 ≤ 1000)
print(solve([1000, 2000], 500))      # 250 (ตัดทั้งคู่)
print(solve([], 100))                # 0 (empty list)