पायथन में एक बैग में गेंदों की न्यूनतम सीमा खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक सरणी संख्या है जहां ith तत्व एक बैग को इंगित करता है जिसमें संख्याएं [i] गेंदों की संख्या होती है। हमारे पास एमएक्स नामक एक और मूल्य भी है। हम निम्नलिखित ऑपरेशन को अधिकतम एमएक्स बार निष्पादित कर सकते हैं -

• गेंदों के किसी भी बैग का चयन करें और इसे कम से कम एक गेंद के साथ दो नए बैग में विभाजित करें।

• यहाँ पेनल्टी एक बैग में गेंदों की अधिकतम संख्या है।

हमें ऑपरेशन के बाद जुर्माने को कम करना होगा। तो अंत में, हमें संचालन करने के बाद न्यूनतम संभव दंड का पता लगाना होगा।

इसलिए, यदि इनपुट संख्या =[4,8,16,4], एमएक्स =4 की तरह है, तो आउटपुट 4 होगा क्योंकि हम निम्नलिखित ऑपरेशन कर सकते हैं:शुरू में हमारे पास [4,8,16,4] जैसे बैग हैं। , [4,8,8,8,4] की तरह 16 गेंदों के साथ विभाजित बैग, फिर 8 गेंदों के साथ प्रत्येक बैग के लिए, उन्हें 4 गेंदों के साथ दो बैगों में विभाजित करें, इसलिए सरणी [4,4,4] की तरह होगी 8,8,4], फिर [4,4,4,4,4,8,4] और अंत में [4,4,4,4,4,4,4,4], तो यहां न्यूनतम 4 गेंदें हैं , वह दंड है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन हेल्पर() को परिभाषित करें। यह लक्ष्य लेगा, एमएक्स

• यदि लक्ष्य 0 के समान है, तो

  • वापसी एमएक्स + 1

• गिनती :=0

• अंकों में प्रत्येक अंक के लिए, करें

  • गिनती :=गिनती + भागफल (संख्या -1)/लक्ष्य

• वापसी गिनती <=एमएक्स

• मुख्य विधि से, निम्न कार्य करें

• बायां :=भागफल का अधिकतम (अंकों के सभी तत्वों का योग /(अंकों का आकार + 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