अजगर में k दिनों में स्काईडाइवर्स के लिए आवश्यक न्यूनतम अंतरिक्ष विमान खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है, जिसे अंक कहा जाता है, जहां प्रत्येक मान उन लोगों के समूह का प्रतिनिधित्व करता है जो एक साथ स्काईडाइव करना चाहते हैं। और हमारे पास एक और मूल्य k है जो दर्शाता है कि वे कितने दिनों तक स्काइडाइविंग के लिए आवेदन कर सकते हैं। हमें उस विमान की न्यूनतम क्षमता का पता लगाना होगा जो हमें k दिनों के भीतर सभी अनुरोधों को पूरा करने में सक्षम होना चाहिए। अनुरोधों को उसी क्रम में पूरा किया जाना चाहिए जिस क्रम में उन्हें दिया गया था और एक विमान दिन में केवल एक बार उड़ान भर सकता है।

इसलिए, यदि इनपुट संख्या =[16, 12, 18, 11, 13], k =3 जैसा है, तो आउटपुट 28 होगा, क्योंकि 28-व्यक्ति हवाई जहाज दिए गए अनुरोधों को [16, 12], [ 18], [11, 13]।

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

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

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

उदाहरण

class Solution:
   def solve(self, nums, k):
      if not nums:
         return 0

      start, end = max(nums), sum(nums)

      while start < end:
         mid = (start + end) // 2

         days = 1
         temp = 0
         for num in nums:
            if temp + num > mid:
               days += 1
               temp = num
            else:
               temp += num

         if days > k:
            start = mid + 1
         else:
            end = mid

      return start

ob = Solution()
nums = [16, 12, 18, 11, 13]
k = 3
print(ob.solve(nums, k))

इनपुट

[16, 12, 18, 11, 13], 3