โปรแกรมหาอัตราการขุดหินน้อยที่สุดใน K ชั่วโมงด้วย Python

คำอธิบายปัญหา

กำหนดลิสต์ piles (จำนวนหินแต่ละกอง) และ k ชั่วโมง ทุกชั่วโมงเลือกกองหนึ่งขุด r หิน (ถ้าน้อยกว่า r ขุดหมดก็ใช้ 1 ชั่วโมง) หา **ค่า r น้อยที่สุด** ที่ขุดหมดทุกกองภายใน ≤ k ชั่วโมง

ตัวอย่าง

piles = [3, 6, 4], k = 5 → Output: 3

r=3: กอง 6 ใช้ 2 ชม., กอง 4 ใช้ 2 ชม., กอง 3 ใช้ 1 ชม. รวม 5 ชม. ✓

ขั้นตอนการแก้ปัญหา (Binary Search)

1. ช่วงคำตอบ: l=1, h=max(piles)
2. ฟังก์ชัน turns(r) = ชั่วโมงที่ใช้ = sum(ceil(pile/r) for pile in piles)
3. Binary search: ถ้า turns(mid) > k → l = mid+1 ไม่งั้น h = mid

การตนการทำงาน (Python)

from math import ceil

def solve(piles, k):
    l, h = 1, max(piles)
    r = h
    def turns(r):
        return sum(ceil(b / r) for b in piles)
    while l < h:
        mid = (l + h) // 2
        if turns(mid) > k:
            l = mid + 1
        else:
            h = mid
            r = min(r, mid)
    return r

piles = [3, 6, 4]
k = 5
print(solve(piles, k))  # Output: 3

อินพุต / เอาต์พุต

Input:  [3, 6, 4], 5
Output: 3