ধরুন আমাদের কাছে পাইল নামক সংখ্যার একটি তালিকা এবং একটি মান k আছে। পাইলস [i] প্রতিনিধিত্ব করে, স্তূপের উপর পাথরের সংখ্যা i. প্রতি ঘন্টায়, আমরা যেকোন স্তূপ নির্বাচন করি এবং সেই স্তূপ থেকে r সংখ্যক পাথর অপসারণ করি। যদি আমরা r-এর চেয়ে কম পাথরের একটি গাদা বাছাই করি, তবে স্তূপটি পরিষ্কার করতে এখনও এক ঘন্টা সময় লাগে। আমাদের r এর ন্যূনতম মান খুঁজে বের করতে হবে, যাতে আমরা k ঘন্টার কম বা সমান সময়ে সমস্ত পাথর অপসারণ করতে পারি।
সুতরাং, যদি ইনপুটটি পাইলস =[3, 6, 4] k =5 এর মত হয়, তাহলে আউটপুট হবে 3, কারণ, r =3টি পাথর প্রতি ঘন্টায়, আমরা 2 ঘন্টার মধ্যে দ্বিতীয় পাইলটি পরিষ্কার করতে পারি, তারপর 2 ঘন্টার মধ্যে তৃতীয়, এবং 1 ঘন্টার মধ্যে প্রথম গাদা পরিষ্কার করুন৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- l :=1
- h :=সর্বাধিক পাইলস
- r :=h
- একটি ফাংশন turns() সংজ্ঞায়িত করুন। এটি r লাগবে
- তালিকায় উপস্থিত সকল উপাদানের যোগফল (পাইলে প্রতিটি b এর জন্য b/r এর সিলিং) সহ
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- যখন l
- মধ্য :=(l + h) / 2 এর তল
- যদি মোড় (মধ্য)> k হয়, তাহলে
- l :=মধ্য + 1
- অন্যথায়,
- h :=মধ্য
- r :=সর্বনিম্ন 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, 6, 4], 5
আউটপুট
3