পাইথনে হাউস এবং নিকটস্থ মেইলবক্সের মধ্যে ন্যূনতম মোট দূরত্ব বের করার প্রোগ্রাম

মান লিজিয়ে আমাদের একটি অ্যারে আছে houses এবং আরেকটি মান k। এখানে houses[i] নির্দেশ করে i-তম বাসার লোকেশন একটি স্ট্রিটের সাথে ধরে। আমাদের স্ট্রিটে kটি মেইলবক্স আলোকেট করতে হবে এবং প্রতিটি বাসা থেকে এর নিকটস্থ মেইলবক্সের দূরত্বের মোট ন্যূনতম করতে হবে।

যেমন, ইনপুট হলে houses = [6,7,9,16,22] এবং k = 2, তবে আউটপুট হবে 9 কারণ যদি মেইলবক্স রাখি ৭ এবং ১৮-এ, তবে মোট দূরত্ব হবে |6-7|+|7-7|+|9-7|+|16-18|+|22-18| = 1+0+2+2+4 = 9।

সমাধানের ধাপসমূহ

houses সর্ট করুন।
util(idx, n, k) ফাংশন ডিফাইন করুন।
যদি k == 1 হয়, তবে:
- core := houses[(n + idx) // 2]
- sum(|houses[i] - core| for i in range(idx, n+1)) রিটার্ন করুন।
result := infinity
i = idx থেকে n পর্যন্ত:
- যদি n - i < k - 1 হয়, তবে ব্রেক করুন।
- result := min(result, util(idx, i, 1) + util(i+1, n, k-1))
result রিটার্ন করুন।
মেইন মেথড থেকে 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