পাইথনের ডাটাবেসে সম্পূর্ণরূপে সংরক্ষণ করার জন্য লগগুলিকে ছেঁটে ফেলার জন্য সবচেয়ে বড় আকারের সন্ধান করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে লগ নামক সংখ্যার একটি তালিকা এবং আরেকটি মান সীমা আছে। লগ[i]-এর প্রতিটি উপাদান i-th ব্যবহারকারীর দ্বারা উত্পন্ন লগের আকার উপস্থাপন করে। এবং সীমা আমাদের ডাটাবেসে সংরক্ষণ করতে পারি এমন লগের মোট আকারের প্রতিনিধিত্ব করে। আমাদেরকে সবচেয়ে বড় x খুঁজে বের করতে হবে যাতে আমরা প্রতিটি লগ ইনকে ছেঁটে ফেলি যাতে সর্বোচ্চ আকার x হয়, এবং বাম লগের আকারের যোগফল সর্বাধিক সীমাতে থাকে। যদি কোনও লগ কাটার প্রয়োজন হয় না, তাহলে কেবল সবচেয়ে বড় লগ সাইজটি ফেরত দিন৷

সুতরাং, যদি ইনপুটটি লগের মত হয় =[500, 200, 10000, 500, 4000] সীমা =3000, তাহলে আউটপুট হবে 900, কারণ আমরা লগগুলিকে 900-এ ছাঁটাই করি, তাহলে আমরা [500, 200, 900, 500 পেতে পারি। , 900] এখন যোগফল 3000

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• lo :=0
• হাই :=1 + সর্বোচ্চ লগ
• যখন lo + 1
• mi :=lo + ফ্লোর অফ (hi - lo)/2
• যদি তালিকায় উপস্থিত সমস্ত উপাদানের যোগফল (প্রতিটি লগ ইন লগের জন্য সর্বনিম্ন মাই এবং লগ) <=সীমা, তারপর
  • lo :=mi
• অন্যথায়,
  • হাই :=মাই

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(logs, limit):
   lo, hi = 0, max(logs) + 1
   while lo + 1 < hi:
      mi = lo + (hi - lo) // 2
      if sum(min(mi, log) for log in logs) <= limit:
         lo = mi
      else:
         hi = mi
   return lo

logs = [500, 200, 10000, 500, 4000]
limit = 3000
print(solve(logs, limit))

ইনপুট

[500, 200, 10000, 500, 4000], 3000

আউটপুট

900