একটি পাইল তালিকা (piles) এবং একটি মান k দেওয়া আছে। piles[i] = i-তম পাইলে পাথরের সংখ্যা। প্রতি ঘণ্টায় যেকোনো একটি পাইল থেকে r সংখ্যক পাথর সরানো যায়। যদি পাইলটিতে r-এর চেয়ে কম পাথর থাকে, তবুও একটি ঘণ্টা লাগে। সর্বনিম্ন r বের করতে হবে যাতে সব পাথর ≤ k ঘণ্টায় সরানো যায়।
সমস্যা উদাহরণ
ইনপুট: piles = [3, 6, 4], k = 5
আউটপুট: 3
ব্যাখ্যা: r = 3 হলে: ২য় পাইল (৬) → ২ ঘণ্টা, ৩য় পাইল (৪) → ২ ঘণ্টা, ১ম পাইল (৩) → ১ ঘণ্টা। মোট ৫ ঘণ্টা।
সমাধানের পদ্ধতি (বাইনারি সার্চ)
l := 1,h := max(piles),r := hturns(r)ফাংশন:sum(ceil(b/r) for b in piles)রিটার্ন করে- বাইনারি সার্চ চালান:
mid = (l + h) // 2- যদি
turns(mid) > kহলেl = mid + 1 - অন্যথায়
h = midএবংr = min(r, mid)
rরিটার্ন করুন
পাইথন কোড
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টেস্ট কেস
ইনপুট: [3, 6, 4], 5
আউটপুট: 3
