পাইথনে হ্রাসমান মূল্য वाले কালারফুল বল বিক্রি কর সর্বোচ্চ প্রফিট বের করার প্রোগ্রাম

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

যেমন, ইনপুট হলে inventory = [5,7], orders = 6, তবে আউটপুট হবে 31 কারণ প্রথম রঙের বল দুবার বিক্রি (৫, ৪), দ্বিতীয় রঙের ৪ বার (৭, ৬, ৫, ৪), মোট প্রফিট 5+4+7+6+5+4 = 31।

সমাধানের ধাপসমূহ

low := 0, high := 10000000
low < high থাকা পর্যন্ত:
- mid := (low + high) // 2
- s := 0
- inventory-এ প্রতিটি i এর জন্য:
  - যদি i > mid হয়, তবে s += i - mid
- যদি s > orders হয়, তবে low := mid + 1
- অন্যথায়, high := mid
mid := (low + high) // 2
ans := 0
inventory-এ প্রতিটি i এর জন্য:
- যদি i > mid হয়, তবে:
  - ans += i*(i+1)//2 - mid*(mid+1)//2
  - orders -= i - mid
ans += orders * mid
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]