Python में घर और निकटतम मेलबॉक्स के बीच न्यूनतम कुल दूरी खोजने का प्रोग्राम

मान लीजिए हमारे पास एक ऐरे houses है और एक मान k है। यहां houses[i] सड़क के किनारे iवें घर का स्थान दर्शाता है, हमें सड़क पर k मेलबॉक्स आवंटित करने हैं, और प्रत्येक घर और उसके निकटतम मेलबॉक्स के बीच न्यूनतम कुल दूरी ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है houses = [6,7,9,16,22], k = 2, तो आउटपुट 9 होगा क्योंकि यदि हम मेलबॉक्स को 7 और 18 पर रखते हैं, तो प्रत्येक घर से न्यूनतम कुल दूरी |6-7|+|7-7|+|9-7|+|16-18|+|22-18| = 1+0+2+2+4 = 9 होगी।

समाधान के चरण

1. houses सूची को सॉर्ट करें
2. util() फंक्शन परिभाषित करें जो idx, n, k लेता है
3. यदि k == 1:
   • core := houses[(n + idx) // 2]
   • sum(|houses[i] - core| for i in range(idx, n+1)) वापस करें
4. result := infinity
5. i को idx से n तक:
   • यदि n - i < k - 1, तो लूप से बाहर निकलें
   • result := min(result, util(idx, i, 1) + util(i+1, n, k-1))
6. result वापस करें
7. मुख्य मेथड से:
   • util(0, len(houses) - 1, k) वापस करें

उदाहरण

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

def solve(houses, k):
    houses.sort()
    def util(idx, n, k):
        if k == 1:
            core = houses[(n + idx) // 2]
            return sum(abs(houses[i] - core) for i in range(idx, n + 1))
        result = float('inf')
        for i in range(idx, n + 1):
            if n - i < k - 1:
                break
            result = min(result, util(idx, i, 1) + util(i+1, n, k - 1))
        return result
    return util(0, len(houses) - 1, k)

houses = [6,7,9,16,22]
k = 2
print(solve(houses, k))

इनपुट

[6,7,9,16,22], 2

आउटपुट

9