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

मान लीजिए हमारे पास एक ऐरे nums है जहां iवां तत्व nums[i] गेंदों वाले बैग को दर्शाता है। हमारे पास एक और मान mx है। हम अधिकतम mx बार निम्नलिखित ऑपरेशन कर सकते हैं:

• गेंदों के किसी भी बैग को चुनें और इसे कम से कम एक गेंद वाले दो नए बैग में विभाजित करें।
• यहां पेनल्टी एक बैग में गेंदों की अधिकतम संख्या है।

हमें ऑपरेशन के बाद पेनल्टी को न्यूनतम करना है। अंत में, हमें ऑपरेशन करने के बाद न्यूनतम संभव पेनल्टी ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है nums = [4,8,16,4], mx = 4, तो आउटपुट 4 होगा क्योंकि हम निम्नलिखित ऑपरेशन कर सकते हैं:

• प्रारंभ में बैग हैं [4,8,16,4]
• 16 गेंदों वाले बैग को विभाजित करें: [4,8,8,8,4]
• प्रत्येक 8 गेंदों वाले बैग को दो 4-4 के बैग में विभाजित करें: [4,4,4,8,8,4]
• फिर [4,4,4,4,4,8,4]
• अंत में [4,4,4,4,4,4,4,4], तो न्यूनतम 4 गेंदें हैं, यही पेनल्टी है।

समाधान के चरण

1. एक फंक्शन helper() परिभाषित करें जो target, mx लेता है
2. यदि target == 0, तो mx + 1 वापस करें
3. count := 0
4. nums में प्रत्येक num के लिए:
   • count := count + (num - 1) // target
5. count <= mx वापस करें
6. मुख्य मेथड से:
   • left := max(sum(nums) // (len(nums) + mx), 1)
   • right := max(nums)
   • while left < right:
     • mid := (left + right) // 2
     • यदि helper(mid, mx) नॉन-ज़ीरो है, तो right := mid
     • अन्यथा, left := mid + 1
   • left वापस करें

उदाहरण

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

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