Python में घटते मूल्य वाली रंगीन गेंदें बेचकर अधिकतम लाभ खोजने का प्रोग्राम

मान लीजिए हमारे पास एक ऐरे inventory है, जहां inventory[i] प्रारंभ में हमारे पास iवें रंग की गेंदों की संख्या दर्शाता है। हमारे पास एक मान orders भी है, जो ग्राहक द्वारा चाही गई गेंदों की कुल संख्या दर्शाता है। हम गेंदों को किसी भी क्रम में बेच सकते हैं। हमारी इन्वेंट्री में अलग-अलग रंग की गेंदें हैं, ग्राहक किसी भी रंग की गेंदें चाहते हैं। अब गेंदों के मूल्य विशेष प्रकृति के हैं। प्रत्येक रंगीन गेंद का मूल्य उस रंग की गेंदों की संख्या है जो हमारी इन्वेंट्री में हैं। तो अगर हमारे पास वर्तमान में 6 नीली गेंदें हैं, तो ग्राहक पहली नीली गेंद के लिए 6 का भुगतान करेगा। फिर केवल 5 नीली गेंदें बचती हैं, तो अगली नीली गेंद का मूल्य 5 होगा। हमें orders रंगीन गेंदें बेचने के बाद मिलने वाले अधिकतम कुल मूल्य को ढूंढना है। यदि उत्तर बहुत बड़ा है, तो इसे मॉड्यूलो 10^9 + 7 वापस करें।

उदाहरण के लिए, यदि इनपुट है inventory = [5,7], orders = 6, तो आउटपुट 31 होगा क्योंकि हम पहले रंग की गेंद को दो बार मूल्य (5,4) पर बेच सकते हैं, और दूसरे रंग की गेंदों को 4 बार (7,6,5,4), तो कुल लाभ 5+4+7+6+5+4 = 31।

समाधान के चरण

1. low := 0, high := 10000000
2. while low < high:
   • mid := (low + high) // 2
   • s := 0
   • inventory में प्रत्येक i के लिए:
     • यदि i > mid:
       • s := s + i - mid
   • यदि s > orders:
     • low := mid + 1
   • अन्यथा:
     • high := mid
3. mid := (low + high) // 2
4. ans := 0
5. inventory में प्रत्येक i के लिए:
   • यदि i > mid:
     • ans := ans + i*(i+1)//2 - mid*(mid+1)//2
     • orders := orders - (i - mid)
6. ans := ans + orders * mid
7. 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))

इनपुट

[5,7], 6

आउटपुट

31