একই শূন্যेतর দৈর্ঘ্যের দুটি পূর্ণসংখ্যা সিকোয়েন্স A আর B দেওয়া আছে। আমরা A[i] আর B[i] сваপ করতে পারি। দুই উপাদানই তাদের নিজস্ব সিকোয়েন্সে একই ইন্ডেক্সে থাকে। কিছু сваপের পর A আর B — দুটোই কঠোরভাবে ক্রমবর্ধমান হবে। উভয় সিকোয়েন্স কঠোরভাবে ক্রমবর্ধমান করতে ন্যূনতম কতগুলো сваপ লাগবে তা বের করতে হবে।
উদাহরণ: A = [1,3,5,4], B = [1,2,3,7] হলে উত্তর ১। যদি A[3] আর B[3] স্বাপ করি, তাহলে A = [1,3,5,7], B = [1,2,3,4] — দুটোই কঠোরভাবে ক্রমবর্ধমান।
সমাধানের ধাপগুলো:
n := A.size(), আকারn-এর দুটি অ্যারেswapCntআরnoSwapCntবানান।swapCnt[0] = 1, noSwapCnt[0] = 0।i = 1থেকেn-1পর্যন্ত:swapCnt[i] := n, noSwapCnt[i] := n- যদি
A[i] > A[i-1] AND B[i] > B[i-1]:noSwapCnt[i] := noSwapCnt[i-1]swapCnt[i] := swapCnt[i-1] + 1
- যদি
A[i] > B[i-1] AND B[i] > A[i-1]:swapCnt[i] := min(swapCnt[i], 1 + noSwapCnt[i-1])noSwapCnt[i] := min(swapCnt[i-1], noSwapCnt[i])
min(swapCnt[n-1], noSwapCnt[n-1])ফেরত দিন।
উদাহরণ (C++)
#include <bits/stdc++.h> using namespace std; class Solution { public: int minSwap(vector<int>& A, vector<int>& B) { int n = A.size(); vector <int> swapCnt(n), noSwapCnt(n); swapCnt[0] = 1; noSwapCnt[0] = 0; for(int i = 1; i < n; i++){ swapCnt[i] = n; noSwapCnt[i] = n; if(A[i] > A[i - 1] && B[i] > B[i - 1]){ noSwapCnt[i] = noSwapCnt[i - 1]; swapCnt[i] = swapCnt[i - 1] + 1; } if(A[i] > B[i - 1] && B[i] > A[i - 1]){ swapCnt[i] = min(swapCnt[i], 1 + noSwapCnt[i - 1]); noSwapCnt[i] = min(swapCnt[i - 1], noSwapCnt[i]); } } return min(swapCnt[n - 1], noSwapCnt[n - 1]); } }; main(){ vector<int> v1 = {1,3,5,4}; vector<int> v2 = {1,2,3,7}; Solution ob; cout << (ob.minSwap(v1, v2)); }ইনপুট
[1,3,5,4] [1,2,3,7]
আউটপুট
1
