पत्थरों के ढेर की सूची piles और एक मान k दिया गया है। piles[i] ढेर i पर पत्थरों की संख्या दर्शाता है। प्रत्येक घंटे, हम किसी भी ढेर को चुनते हैं और उससे r पत्थर हटाते हैं। यदि हम r से कम पत्थरों वाला ढेर चुनते हैं, तो उसे खाली करने में भी एक घंटा लगता है। हमें r का न्यूनतम मान खोजना है जिससे हम सभी पत्थरों को k घंटे या उससे कम में हटा सकें।
उदाहरण
इनपुट: piles = [3, 6, 4], k = 5
आउटपुट: 3
व्याख्या: r = 3 पत्थर प्रति घंटे की दर से, हम दूसरे ढेर को 2 घंटे में खाली कर सकते हैं, तीसरे को 2 घंटे में, और पहले को 1 घंटे में। कुल 5 घंटे।
एल्गोरिदम (बाइनरी सर्च)
l := 1(न्यूनतम संभव दर)h := max(piles)(अधिकतम संभव दर)r := hturns(r)फंक्शन परिभाषित करें जोsum(ceil(b / r) for b in piles)लौटाता है- जब
l < h:mid := (l + h) // 2- यदि
turns(mid) > k:l := mid + 1 - अन्यथा:
h := mid,r := min(r, mid)
rलौटाएं
Python कार्यान्वयन
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)) # आउटपुट: 3
इनपुट/आउटपुट
Input: [3, 6, 4], 5
Output: 3