পাইথনে দুটি শহরে সমান সংখ্যক মানুষ পাঠানোর ন্যূনতম খরচ গণনা করার প্রোগ্রাম

পাইথনে একটি কস্ট লিস্ট costs দেওয়া আছে, যেখানে costs[i] = [c1, c2] বোঝায়: i-তম ব্যক্তিকে শহর ০-এ পাঠালে খরচ c1 এবং শহর ১-এ পাঠালে খরচ c2। দুটি শহরে সমান সংখ্যক মানুষ পাঠাতে হবে। ন্যূনতম মোট খরচ বের করতে হবে।

উদাহরণ

ইনপুট: costs = [[2, 6], [10, 3], [4, 9], [5, 8]]

আউটপুট: 17

ব্যাখ্যা:

• ব্যক্তি ০ এবং ২ -> শহর ০: খরচ ২ + ৪ = ৬
• ব্যক্তি ১ এবং ৩ -> শহর ১: খরচ ৩ + ৮ = ১১
• মোট: ৬ + ১১ = ১৭

এলগরিদম (গ্রিডি + সর্টিং)

1. s = 0 (প্রাথমিক খরচ: সবাই শহর ০-এ যায় ধরে)
2. a = [] (খরচ পার্থক্য লিস্ট: শহর ১ - শহর ০)
3. প্রতিটি (x, y) in costs এর জন্য:
   • s += x (শহর ০-এ পাঠানোর খরচ যোগ)
   • a.append(y - x) (শহর ১-এ পাঠালে অতিরিক্ত খরচ/বাঁচত)
4. a সর্ট করুন (অর্ডমে) — সবচেয়ে কম অতিরিক্ত খরচ (বা সবচেয়ে বেশি বাঁচত) আগে আসবে
5. প্রথম len(a)//2 টি এলিমেন্ট s-তে যোগ করুন (এগুলোকে শহর ১-এ পাঠানো)
6. s রিটার্ন করুন

পাইথন ইমপ্লিমেন্টেশন

def solve(costs):
    s = 0
    a = []
    for x, y in costs:
        s += x
        a += (y - x,)
    a.sort()
    for i in range(len(a) // 2):
        s += a[i]
    return s

costs = [[2, 6], [10, 3], [4, 9], [5, 8]]
print(solve(costs))  # Output: 17

ইনপুট

[[2, 6], [10, 3], [4, 9], [5, 8]]

আউটপুট

17

ব্যাখ্যা

• প্রথমে ধরে নেওয়া হয় সবাই শহর ০-এ যাচ্ছে: মোট খরচ = ২+১০+৪+৫ = ২১
• পার্থক্য (y-x): [৪, -৭, ৫, ৩]
• সর্টেড: [-৭, ৩, ৪, ৫]
• প্রথম ২টি (ন半数) যোগ: -৭ + ৩ = -৪
• ফাইনাল খরচ: ২১ + (-৪) = ১৭

ইন্টুইশন: y - x ছোট (নেগেটিভ) হলে অর্থাৎ শহর ১-এ পাঠালে খরচ কম -> সেগুলোকে শহর ১-এ পাঠানো উচিত। সর্ট করে প্রথম অর্ধেকটিকে শহর ১-এ পাঠালে ন্যূনতম খরচ নিশ্চিত হয়।

সময় জটিলতা

O(n log n) (সর্টিং-এর কারণে), স্পেস: O(n)।