পাইথনে একটি ব্যাগে ন্যূনতম বল সীমা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে সংখ্যা আছে যেখানে ith উপাদানটি একটি ব্যাগ নির্দেশ করে যেখানে nums[i] বল রয়েছে। আমরা mx নামক আরেকটি মান আছে. আমরা সর্বাধিক mx বার −

• বলগুলির যেকোন ব্যাগ নির্বাচন করুন এবং কমপক্ষে একটি বল সহ দুটি নতুন ব্যাগে ভাগ করুন।

• এখানে পেনাল্টি হল একটি ব্যাগে সর্বোচ্চ সংখ্যক বল।

অপারেশনের পর আমাদের শাস্তি কমাতে হবে। তাই পরিশেষে, অপারেশন করার পর আমাদের ন্যূনতম সম্ভাব্য শাস্তি খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি nums =[4,8,16,4], mx =4 এর মত হয়, তাহলে আউটপুট হবে 4 কারণ আমরা নিম্নলিখিত ক্রিয়াকলাপগুলি সম্পাদন করতে পারি:প্রাথমিকভাবে আমাদের [4,8,16,4] এর মতো ব্যাগ রয়েছে। , 16 টি বলের মত ব্যাগ বিভক্ত করুন [4,8,8,8,4], তারপর প্রতিটি ব্যাগের জন্য 8 টি বলে, তাদের দুটি ব্যাগে বিভক্ত করুন প্রতিটি 4 বল সহ, তাহলে অ্যারে হবে [4,4,4, 8,8,4], তারপর [4,4,4,4,4,8,4] এবং অবশেষে [4,4,4,4,4,4,4,4], তাই এখানে সর্বনিম্ন 4টি বল আছে , এটাই শাস্তি৷

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

• একটি ফাংশন হেল্পার() সংজ্ঞায়িত করুন। এটি লক্ষ্য, mx

  নেবে

• যদি লক্ষ্য 0 এর মত হয়, তাহলে

  • ফিরুন mx + 1

• গণনা :=0

• প্রতিটি সংখ্যার জন্য, করুন

  • গণনা :=গণনা + ভাগফল (সংখ্যা - 1)/লক্ষ্য

• ফেরত সংখ্যা <=mx

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন

• বাম :=(সংখ্যার সমস্ত উপাদানের যোগফল /(সংখ্যার আকার + mx)) এবং 1

  -এর সর্বোচ্চ ভাগফল

• ডান :=সংখ্যার সর্বোচ্চ

• যখন বামে <ডানে, কর

  • মধ্য :=(বাম + ডান)/2

    এর ভাগফল

  • যদি সহায়ক (মিড, এমএক্স) অ-শূন্য হয়, তাহলে

    • ডান :=মধ্য

  • অন্যথায়,

    • বাম :=মধ্য + 1

• বাম দিকে ফিরুন

উদাহরণ

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

def helper(target, mx):
   if target == 0:
      return mx + 1
   count = 0
   for num in nums:
      count += (num - 1) // target
   return count <= mx

def solve(nums, mx):
   left, right = max(sum(nums) // (len(nums) + mx), 1), max(nums)
   while left < right:
      mid = (left + right) // 2
      if helper(mid, mx):
         right = mid
      else:
         left = mid + 1
   return left

nums = [4,8,16,4]
mx = 4
print(solve(nums, mx))

ইনপুট

[4,8,16,4], 4

আউটপুট

4