पायथन में समान लंबाई के k रिबन की अधिकतम लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास सकारात्मक संख्याओं की एक सूची है, जो रिबन की लंबाई का प्रतिनिधित्व करती है और एक मान k भी है। हम जितनी बार चाहें रिबन काट सकते हैं, हमें सबसे बड़ी लंबाई r ढूंढनी होगी जैसे कि हमारे पास लंबाई r के k रिबन हो सकें। अगर हमें ऐसा समाधान नहीं मिल रहा है, तो -1 पर लौटें।

इसलिए, यदि इनपुट रिबन की तरह है =[1, 2, 5, 7, 15] k =5, तो आउटपुट 5 होगा, क्योंकि हम आकार 15 के रिबन को 5 प्रत्येक लंबाई के 3 टुकड़ों में काट सकते हैं। फिर आकार 7 के रिबन को 2 और 5 के आकार में काटें। और आकार 5 का एक और रिबन है, इसलिए हमें कुल आकार 5 में 5 रिबन मिल रहे हैं।

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

• बाएं:=0
• दाएं:=अधिकतम रिबन
• बाएं <दाएं, करते हैं
  • मध्य :=तल (बाएं + दाएं + 1) / 2
  • यदि सूची में मौजूद सभी तत्वों का योग है (रिबन का फर्श प्रत्येक रिबन के लिए लेन / मध्य रिबन में लेन जो कम से कम k है), तो
    • बाएं:=मध्य
  • अन्यथा,
    • दाएं:=मध्य -1
• अगर बायां गैर-शून्य है, तो
  • बाएं लौटें
• वापसी -1

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def solve(ribbons, k):
   left = 0
   right = max(ribbons)
   while left < right:
      mid = (left + right + 1) // 2
      if sum((ribbonLen // mid for ribbonLen in ribbons)) >= k:
         left = mid
      else:
         right = mid - 1
   if left:
      return left
   return -1

ribbons = [1, 2, 5, 7, 15]
k = 5
print(solve(ribbons, k))

इनपुट

[1, 2, 5, 7, 15], 5

आउटपुट

5