SPOJ - BOOKS1 - Copying Books Tutorial
Topics of this problem: Binary Search + Greedy
১) এই প্রব্লেমে আমরা শুরুতে একটা ফাংশন বানাবো যার কাজ হবে একটা ভ্যালু প্যারামিটার হিসেবে নিয়ে দেখা যে প্রত্যেক লেখক কে দিয়ে সর্বোচ্চ এতোগুলো পেইজ লিখালে K সংখ্যক লেখক m টি বই লিখে শেষ করতে পারবে কি না। যদি পারে তাহলে True রিটার্ন করবে নাহয় False রিটার্ন করবে।
২) এরপর বাইনারী সার্চের কাজ করবো। বাইনারী সার্চের Low হবে ১টি বইয়ে সর্বোচ্চ যতগুলো পেইজ আছে ততো। High হবে 5e9 । এবার বাইনারী সার্চের মাধ্যমে বের করবো সর্বনিম্ন কোন ভ্যালুর জন্য Valid ফাংশন True রিটার্ন করে। প্রত্যেক লেখক কে দিয়ে সর্বোচ্চ ততোগুলো পেইজ লিখানো যাবে।
৩) সলুশ্যন এর বাকি অংশ গ্রীডি পার্ট। এবার শেষ বই থেকে শুরু করে প্রথম বই পর্যন্ত লুপ চালিয়ে দেখবো ১ জন লেখক কে সিকুয়েন্সিয়ালি সর্বোচ্চ যতো পেইজ লিখতে দেয়া যায়। শেষ থেকে লুপ চালাবো এজন্য যাতে করে ১ম দিকের লেখক দের কে যতো সম্ভব কম সংখ্যক পেইজ লিখতে দেয়া যায় যেভাবে প্রব্লেমে বলা আছে।
Comments
Post a Comment