Giả sử chúng ta có một danh sách các số được gọi là cọc và một giá trị k. Các cọc [i] đại diện cho số lượng đá trên cọc i. Vào mỗi giờ, chúng tôi chọn một đống bất kỳ và loại bỏ r số đá từ đống đó. Nếu chúng ta chọn một đống có ít hơn r viên đá, thì vẫn phải mất một giờ để dọn đống đó. Chúng ta phải tìm giá trị nhỏ nhất của r sao cho chúng ta có thể loại bỏ tất cả các viên đá trong thời gian ít hơn hoặc bằng k giờ.
Vì vậy, nếu đầu vào giống như cọc =[3, 6, 4] k =5, thì đầu ra sẽ là 3, bởi vì, với r =3 viên đá mỗi giờ, chúng ta có thể dọn sạch đống thứ hai trong 2 giờ, sau đó xóa thứ ba trong 2 giờ và dọn sạch đống đầu tiên sau 1 giờ.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- l:=1
- h:=tối đa số lượng cọc
- r:=h
- Xác định một hàm turn (). Điều này sẽ mất r
- trả về tổng của tất cả các phần tử có trong danh sách với (trần của b / r cho mỗi b trong các đống)
- Từ phương pháp chính, hãy thực hiện như sau -
- while l
- giữa:=tầng của (l + h) / 2
- nếu lượt (giữa)> k, thì
- l:=mid + 1
- nếu không,
- h:=mid
- r:=tối thiểu của r và giữa
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
from math import ceil def solve(piles, k): l = 1 h = 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))
Đầu vào
[3, 6, 4], 5
Đầu ra
3