Python में बाल्टी में गेंदों के बीच न्यूनतम बल को अधिकतम करने का प्रोग्राम

मान लीजिए हमें कई बाल्टियाँ और x संख्या में गेंदें दी गई हैं। यदि गेंदों को बाल्टी में डाला जाता है, तो उनके भीतर एक विशेष बल कार्य करता है और हमें गेंदों को इस तरह रखने का तरीका ढूंढना है कि दो गेंदों के बीच न्यूनतम बल अधिकतम हो। पोजीशन p और q की बाल्टी में दो गेंदों के बीच बल |p - q| है। हमें दिया गया इनपुट बाल्टी पोजीशन वाला ऐरे और गेंदों की संख्या x है। हमें उनके बीच न्यूनतम बल ढूंढना है।

उदाहरण के लिए, यदि इनपुट है pos = [2, 4, 6, 8, 10, 12], x = 3, तो आउटपुट 4 होगा।

गेंदों को 12 बाल्टियों के दिए गए पोजीशन में ऐरे में रखा जा सकता है। तीन गेंदों को पोजीशन 4, 8, और 12 में रखा जा सकता है और उनके बीच बल 4 होगा। इस मान को और बढ़ाया नहीं जा सकता।

समाधान के चरण

1. ball_count() फंक्शन परिभाषित करें जो d लेता है:
   • ans := 1
   • curr := pos[0]
   • i को 1 से n तक:
     • यदि pos[i] - curr >= d:
       • ans := ans + 1
       • curr := pos[i]
   • ans वापस करें
2. n := len(pos)
3. pos सूची को सॉर्ट करें
4. left := 0
5. right := pos[-1] - pos[0]
6. while left < right:
   • mid := right - (right - left) // 2
   • यदि ball_count(mid) >= x:
     • left := mid
   • अन्यथा:
     • right := mid - 1
7. left वापस करें

उदाहरण

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

def solve(pos, x):
    n = len(pos)
    pos.sort()
    def ball_count(d):
        ans, curr = 1, pos[0]
        for i in range(1, n):
            if pos[i] - curr >= d:
                ans += 1
                curr = pos[i]
        return ans
    left, right = 0, pos[-1] - pos[0]
    while left < right:
        mid = right - (right - left) // 2
        if ball_count(mid) >= x:
            left = mid
        else:
            right = mid - 1
    return left

print(solve([2, 4, 6, 8, 10, 12], 3))

इनपुट

[2, 4, 6, 8, 10, 12], 3

आउटपुट

4