Chương trình Python tìm tốc độ đào đá tối thiểu để hoàn thành trong K giờ

Cho danh sách piles (số đá mỗi đống) và số giờ k. Mỗi giờ chọn một đống, đào r viên đá. Nếu đống còn < r viên, vẫn mất 1 giờ để đào hết. Tìm r nhỏ nhất để đào hết tất cả đống trong ≤ k giờ.

Ví dụ

Input: piles = [3, 6, 4], k = 5

Output: 3

Giải thích: r=3 → đống 6: 2h, đống 4: 2h, đống 3: 1h → tổng 5h.

Thuật toán (Binary Search)

1. Khoảng tìm kiếm: left = 1, right = max(piles).
2. Hàm turns(r) tính tổng giờ cần: sum(ceil(pile / r) for pile in piles).
3. Binary search:
   • mid = (left + right) // 2
   • Nếu turns(mid) > k → left = mid + 1 (cần đào nhanh hơn)
   • Ngược lại → right = mid, cập nhật kết quả.

Mã nguồn Python

from math import ceil

def solve(piles, k):
    left, right = 1, max(piles)
    ans = right

    def turns(r):
        return sum(ceil(pile / r) for pile in piles)

    while left < right:
        mid = (left + right) // 2
        if turns(mid) > k:
            left = mid + 1
        else:
            right = mid
            ans = min(ans, mid)

    return ans

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

Độ phức tạp

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