এই টিউটোরিয়ালে দুটি অ্যারে A এবং B দেওয়া আছে। আমাদের A-এর যেকোনো একটি পারমুটেশন আউটপুট করতে হবে যাতে A[i] > B[i] হয় এমন ইনডেক্সের সংখ্যা সর্বাধিক হয়। উদাহরণ −
ইনপুট: A = [12, 22, 41, 13], B = [1, 20, 10, 12] আউটপুট: 12, 22, 41, 13 ইনপুট: A = [2, 5, 9, 7], B = [1, 12, 4, 54] আউটপুট: 2 7 5 9 একাধিক উত্তর থাকতে পারে, যেকোনো একটি প্রিন্ট করলেই চলবে।
এই সমস্যাতেই, আমাদের A[i] > B[i] হয় এমন ইনডেক্স maksimize করতে হবে, তাই আমরা লালচী (greedy) পদ্ধতিতে সমাধান করব।
এই পদ্ধতিতে, আমরা প্রথমে দুটি অ্যারে সর্ট করব। এখন লালচীভাবে B-এর প্রতিটি ইনডেক্স চেক করব যাতে A[i] তার চেয়ে বড় হয় এবং সেই এলিমেন্টকে একটি ভেক্টরে রাখব।
#include <bits/stdc++.h> using namespace std; int main(){ int A[] = { 2, 5, 9, 7 }; int B[] = { 1, 12, 4, 54 }; int n = sizeof(A) / sizeof(int); // অ্যারে সাইজ vector<pair<int, int> > A_pair, B_pair; /***********************এলিমেন্টকে তার পজিশনের সাথে লিংক করা***********/ for (int i = 0; i < n; i++) A_pair.push_back({A[i], i}); for (int i = 0; i < n; i++) B_pair.push_back({B[i], i}); /***********************************************************************/ /*****পেয়ার ভেক্টরগুলো সর্ট করা********************/ sort(A_pair.begin(), A_pair.end()); sort(B_pair.begin(), B_pair.end()); int i = 0, j = 0, ans[n]; memset(ans, -1, sizeof(ans)); // সব এলিমেন্ট -1 দিয়ে ইনিশিয়ালাইজ vector<int> remaining; // যেসব এলিমেন্ট B-এ ছোট সেগুলো রাখবে while (i < n && j < n) { // অ্যারে সর্টেড থাকায় যদি বর্তমান ইনডেক্সে A-এর এলিমেন্ট B-এর এলিমেন্টের চেয়ে ছোট হয় // তবে সেটি B-এর অন্য এলিমেন্টের চেয়েও ছোট হবে, তাই সেটি remaining-এ রাখা if (A_pair[i].first > B_pair[j].first) { ans[B_pair[j].second] = A_pair[i].first; i++; j++; } else { remaining.push_back(i); i++; } } j = 0; for (int i = 0; i < n; ++i){ // যদি ans-র কোনো ইনডেক্স অপরিবর্তিত থাকে তবে // সেটি remaining ভেক্টরের এলিমেন্ট দিয়ে পূরণ করা if (ans[i] == -1){ ans[i] = A_pair[remaining[j]].first; j++; } } for (int i = 0; i < n; i++) // উত্তর প্রিন্ট cout << ans[i] << " "; return 0; }
2 7 5 9
এই পদ্ধতিতে, আমরা প্রথমে সব এলিমেন্টকে তার ইনডেক্সের সাথে লিংক করি যাতে সর্ট করার পরও পুরনো ইনডেক্স পাওয়া যায়। দুটি পেয়ার ভেক্টর সর্ট করা হয়। এখন লালচীভাবে দুটি অ্যারে ট্রাভার্স করি: যদি A_pair-এর কোনো ইনডেক্সের মান B_pair-এর বর্তমান ইনডেক্সের মানের চেয়ে বড় হয়, তবে সেটি ans অ্যারেতে রাখি (B_pair-এর পজিশনে)। না হলে, যেহেতু দুটি ভেক্টর সর্টেড, সেই A_pair এলিমেন্টটি আর কাজে লাগবে না, তাই তার ইনডেক্স remaining ভেক্টরে রাখি। শেষে remaining ভেক্টরের সাহায্যে ans অ্যারেটি পূরণ করে প্রিন্ট করি।
এই টিউটোরিয়ালে আমরা একটি অ্যারের পারমুটেশন বের করেছি যাতে অন্য অ্যারেতে ছোট মান পাওয়া যায়। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।
