পাইথনে কম-মূল্যবান রঙিন বল বিক্রি করে সর্বাধিক মুনাফা খোঁজার প্রোগ্রাম

ধরুন আমাদের ইনভেন্টরি নামে একটি অ্যারে আছে, যেখানে ইনভেন্টরি [i] ith রঙের বলের সংখ্যা উপস্থাপন করে যা আমরা প্রাথমিকভাবে পেয়েছি। আমাদের কাছে অর্ডার নামে একটি মানও রয়েছে, যা গ্রাহকের চাওয়া মোট বল সংখ্যার প্রতিনিধিত্ব করে। আমরা যেকোনো ক্রমে বল বিক্রি করতে পারি। আমাদের ইনভেন্টরিতে বিভিন্ন রঙের বল রয়েছে, গ্রাহকরা যেকোনো রঙের বল চান। এখন বলের মান প্রকৃতিতে বিশেষ। প্রতিটি রঙিন বলের মান হল সেই রঙের বলের সংখ্যা যা আমাদের তালিকায় রয়েছে। তাই যদি বর্তমানে আমাদের কাছে 6 টি নীল বল থাকে, তাহলে গ্রাহক প্রথম নীল বলের জন্য 6 টাকা দিতে হবে। তারপরে শুধুমাত্র 5টি নীল বল বাকি আছে, তাই পরবর্তী নীল বলের মূল্য 5 হবে। আমাদের অর্ডার রঙিন বল বিক্রি করার পরে আমরা যে সর্বোচ্চ মোট মূল্য পেতে পারি তা খুঁজে বের করতে হবে। উত্তরটি খুব বড় হলে, 10^9 + 7.

মডিউলটি ফেরত দিন

সুতরাং, যদি ইনপুটটি ইনভেন্টরি =[5,7], অর্ডার =6 এর মতো হয়, তাহলে আউটপুট হবে 31 কারণ আমরা প্রথম রঙিন বলটি দুইবার দামে (5,4) এবং দ্বিতীয় রঙের বল 4 বার (7) বিক্রি করতে পারি। ,6,5,4), তাই মোট লাভ 5+4+7+6+5+4 =31

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

কম :=0, উচ্চ :=10000000
যখন কম <উচ্চ, করুন
- মধ্য :=(নিম্ন + উচ্চ)/2
  এর ভাগফল
- s :=0
- প্রতিটি i ইনভেন্টরির জন্য, করুন
  - যদি আমি> মধ্য, তাহলে
    - s :=s + i - mid
- যদি s> আদেশ দেয়, তাহলে
  - নিম্ন :=মধ্য + 1
- অন্যথায়,
  - উচ্চ :=মধ্য
মধ্য :=(নিম্ন + উচ্চ)/2
এর ভাগফল
উত্তর :=0
প্রতিটি i ইনভেন্টরির জন্য, করুন
- যদি আমি> মধ্য, তাহলে
  - উত্তর :=উত্তর + (i*(i+1)/2)-এর ভাগফল - (মধ্য*(মধ্য+1)/2)
  - অর্ডার :=অর্ডার - আই-মিড
ans :=ans + অর্ডার * মাঝামাঝি
উত্তর দিন মোড (10^9 + 7)

উদাহরণ

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

def solve(inventory, orders):
   low = 0
   high = 10000000

   while low < high:
      mid = (low+high)//2

      s = 0
      for i in inventory:
         if i > mid:
            s += i-mid

      if s > orders:
         low = mid+1
      else:
         high = mid


   mid = (low+high)//2

   ans = 0
   for i in inventory:
      if i > mid:
         ans += i*(i+1)//2 - mid*(mid+1)//2
         orders -= i-mid

   ans += orders*mid
   return ans % (10**9 + 7)

inventory = [5,7]
orders = 6
print(solve(inventory, orders))

ইনপুট

[6,8,7,11,5,9], [0,0,2], [2,3,5]