ধরুন আমাদের N উপাদান বিশিষ্ট একটি অ্যারে আছে। আমাদের অ্যারে থেকে উপাদান মুছে ফেলতে হবে দেওয়া অপারেশন অনুসরণ করে। অপারেশনটি হল: অ্যারে থেকে যেকোনো দুটি সংখ্যা বেছে নিতে হবে, এবং বড়টি মুছে ফেলতে হবে। এই অপারেশনে খরচ হবে ছোট সংখ্যাটির সমান। আমাদের একবারে শুধু একটি উপাদান মুছে ফেলতে হবে, এই অপারেশন অনুযায়ী, এবং ন্যূনতম খরচে কাজটি সম্পন্ন করতে হবে। ধরুন অ্যারেটি হল {4, 2, 5}। আমি ৪ এবং ২ নিলাম, খরচ ২ দিয়ে ৪ মুছে ফেললাম, তারপর আবার ৫ মুছে ফেললাম খরচ ২ দিয়ে।
পদ্ধতিটি খুব সহজ। যেহেতু খরচ হবে ছোট সংখ্যাটির সমান, তাই খরচ কমানোর জন্য সবচেয়ে ছোট উপাদানটি এবং অন্য কোনো উপাদান নিয়ে বড়টি মুছে ফেলব, খরচ সবসময় ছোট সংখ্যাটিই থাকবে। তাই মোট খরচ হবে (N - 1) * সবচেয়ে ছোট সংখ্যা।
C++ প্রোগ্রাম উদাহরণ
#include <iostream>
#include <algorithm>
using namespace std;
int getMinimumCost(int arr[], int n) {
int smallest = *min_element(arr, arr+n);
return smallest * (n - 1);
}
int main() {
int arr[] = { 4, 2, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Minimum cost: " << getMinimumCost(arr, n);
return 0;
}
আউটপুট
Minimum cost: 4
