Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

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

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

उदाहरण

इनपुट: ribbons = [1, 2, 5, 7, 15], k = 5

आउटपुट: 5

व्याख्या: हम आकार 15 के रिबन को लंबाई 5 के 3 टुकड़ों में काट सकते हैं। फिर आकार 7 के रिबन को आकार 2 और 5 में काटें। और एक रिबन आकार 5 का पहले से है, इसलिए हमें कुल 5 रिबन आकार 5 के मिलते हैं।

एल्गोरिदम (बाइनरी सर्च)

  1. left := 0
  2. right := max(ribbons)
  3. जब left < right:
    • mid := (left + right + 1) // 2
    • यदि sum(ribbonLen // mid for ribbonLen in ribbons) >= k: left := mid
    • अन्यथा: right := mid - 1
  4. यदि left शून्येतर है: left लौटाएं
  5. अन्यथा: -1 लौटाएं

Python कार्यान्वयन

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))  # आउटपुट: 5

इनपुट/आउटपुट

Input: [1, 2, 5, 7, 15], 5
Output: 5
  1. - Python प्रोग्राम - रॉड काटकर और समान लंबाई के रॉड बेचकर अधिकतम लाभ

    रॉड की लंबाई की सूची rodLen दी गई है। दो पूर्णांक profit (प्रति यूनिट लंबाई लाभ) और cost (प्रति कट लागत) भी दिए गए हैं। हम प्रति यूनिट लंबाई पर लाभ कमा सकते हैं लेकिन केवल वही रॉड बेच सकते हैं जो सभी समान लंबाई के हों। हम एक रॉड को दो टुकड़ों में काट सकते हैं ताकि उनकी लंबाई पूर्णांक हो, लेकिन प्रत्

  1. - पायथन में समान आवृत्ति वाले अधिकतम बारंबार तत्व के साथ सबसे छोटे सबलिस्ट की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। यदि nums में सबसे अधिक बारंबार संख्या की आवृत्ति k है। हमें सबसे छोटे सबलिस्ट की लंबाई ढूंढनी है जैसे कि उसके सबसे अधिक बारंबार आइटम की आवृत्ति भी k हो। इसलिए, यदि इनपुट है nums = [10, 20, 30, 40, 30, 10], तो आउटपुट होगा 3, क्योंकि यहां सबसे अधिक

  1. Python में इमारतों की अधिकतम ऊंचाई ज्ञात करें Python में इमारतों की अधिकतम ऊंचाई ज्ञात करें

    n इमारतें एक पंक्ति में (1 से n लेबल)। प्रतिबंध: restrictions[i] = (id, max_height)। नियम: ऊंचाई ≥ 0, पहली इमारत की ऊंचाई = 0, आसन्न इमारतों में ऊंचाई अंतर ≤ 1। अधिकतम संभव ऊंचाई खोजें। एल्गोरिदम: दो पास + शिखर गणना प्रतिबंधों को id द्वारा सॉर्ट करें फॉरवर्ड पास: बाएं से दाएं, प्रत्येक प्रतिबंध को