এই আর্টিকেলে, আমরা একটি দেয়া অ্যারে n সংখ্যা দিয়ে রি-অ্যারেঞ্জ করার সমস্যা আলোচনা করব। মূলত, আমাদের অ্যারে থেকে উপাদান সিলেক্ট করতে হবে। প্রতিটি উপাদান সিলেক্ট করার জন্য আমরা কিছু পয়েন্ট পাবো যা বর্তমান উপাদানের মান * বর্তমান উপাদানের আগে সিলেক্ট করা উপাদান সংখ্যা দিয়ে ইভ্যালুয়েট হবে। আপনাকে উপাদান সিলেক্ট করতে হবে যেন ম্যাক্সিমাম পয়েন্ট পাওয়া যায়। উদাহরণস্বরূপ −
ইনপুট : arr[ ] = { 3, 1, 5, 6, 3 }
যদি আমরা উপাদানগুলো দেওয়া অর্ডারে সিলেক্ট করি, আমাদের পয়েন্ট হবে
= 3 * 0 + 1 * 1 + 5 * 2 + 6 * 3 + 3 * 4
= 41
পয়েন্ট ম্যাক্সিমাইজ করতে হলে উপাদানগুলো এই অর্ডারে সিলেক্ট করতে হবে { 1, 3, 3, 5, 6 }
= 1 * 0 + 3 * 1 + 3 * 2 + 5 * 3 + 6 * 4
= 48 (ম্যাক্সিমাম)
আউটপুট : 48
ইনপুট : arr[ ] = { 2, 4, 7, 1, 8 }
আউটপুট : 63
সমাধানের পদ্ধতি
উদাহরণটি দেখে আমরা বুঝতে পারি যে ম্যাক্সিমাম পয়েন্ট পেতে হলে উপাদানগুলো ছোট থেকে বড়ের দিকে সিলেক্ট করতে হবে। সমাধান খুঁজে বের করার পদ্ধতি হল,
- দেয়া অ্যারেটি অ্যাসেন্ডিং অর্ডারে সর্ট করুন।
- ইনডেক্স ০ থেকে শেষ পর্যন্ত উপাদান সিলেক্ট করা শুরু করুন।
- প্রতিটি উপাদান সিলেক্ট করলে প্রাপ্ত পয়েন্ট ক্যালকুলেট করুন।
উদাহরণ প্রোগ্রাম
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main() {
int arr[] = { 2, 4, 7, 1, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
// অ্যারে সর্ট করা
sort(arr, arr + n);
int points = 0;
// অ্যারে ট্রাভার্স করে পয়েন্ট ক্যালকুলেট করা
for (int i = 0; i < n; i++) {
points += arr[i] * i;
}
cout << "Maximum points: " << points;
return 0;
}
আউটপুট
Maximum points: 63
উপরোক্ত কোডের ব্যাখ্যা
এই C++ কোড বুঝতে খুব সহজ। প্রথমে আমরা অ্যারে সর্ট করি এবং তারপর একটি ফর লুপ দিয়ে অ্যারে ট্রাভার্স করি এবং শুরু থেকে শেষ পর্যন্ত প্রতিটি উপাদান সিলেক্ট করলে প্রাপ্ত পয়েন্ট ক্যালকুলেট করি।
উপসংহার
এই আর্টিকেলে, আমরা অ্যারেতে উপাদান সিলেক্ট করলে i * arr[i] ফর্মুলা দিয়ে পয়েন্ট ক্যালকুলেট হয় এমন একটি সমস্যা আলোচনা করেছি। আমরা গ্রিডি অ্যালগরিদম প্রয়োগ করে এই সমস্যা সমাধান করেছি এবং ম্যাক্সিমাম পয়েন্ট পেয়েছি। C++ কোডও আলোচনা করেছি, আমরা এই কোড যেকোনো অন্য ল্যাঙ্গুয়েজে লিখতে পারি như C, Java, Python, ইত্যাদি। আশা করি আপনি এই আর্টিকেলটিকে সহায়ক খুঁজে পাবেন।
