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

मान लीजिए कि हमारे पास एक सरणी है, जिसे इन्वेंट्री कहा जाता है, जहां इन्वेंट्री [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
- एस:=0
- सूची में प्रत्येक i के लिए, करें
  - अगर मैं> मध्य, तो
    - s :=s + i - मध्य
- अगर s> आदेश, तो
  - कम :=मध्य + 1
- अन्यथा,
  - उच्च :=मध्य
मध्य :=भागफल (निम्न + उच्च)/2
उत्तर :=0
सूची में प्रत्येक i के लिए, करें
- अगर मैं> मध्य, तो
  - उत्तर :=उत्तर + (i*(i+1)/2) का भागफल - (मध्य*(मध्य+1)/2) का भागफल
  - आदेश:=आदेश - मैं-मध्य
उत्तर:=उत्तर + आदेश * मध्य
वापसी उत्तर मोड (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]