মনে করুন, একটি অ্যারে আছে। এই অ্যারেতে একটি জোড়া (A[i], A[j]) কে "গুরুত্বপূর্ণ রিভার্স পেয়ার" বলা হবে যদি i < j এবং A[i] > 2*nums[j]। গুরুত্বপূর্ণ রিভার্স পেয়ারগুলোর সংখ্যা বের করতে হবে।
ইনপুট [2,8,7,7,2] হলে, ফলাফল ৩।
সমাধানের ধাপসমূহ
- ans := 0
- merge(a, low, mid, high) ফাংশন: মার্জ সর্টের মত মিশ্রণ করুন, সাথে সাথে রিভার্স পেয়ার গণনা করুন
- দুটি পয়েন্টার i, j এবং first পয়েন্টার ব্যবহার করুন
- যখন a[first]*2 < a[i], first++
- মার্জ করার সময় ans += first - (mid+1)
- calc(a, low, high) ফাংশন: ডিভাইড এন্ড কনকর করে merge() কল করুন
- solve(A) ফাংশন: ans=0, calc(A, 0, n-1), ans রিটার্ন
উদাহরণ
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int ans = 0; void merge(vector <int> &a, lli low, lli mid, lli high){ lli k = high - low + 1; vector <lli> temp(k); lli i = low, j = mid + 1; k = 0; lli first = mid + 1; while(i <= mid){ while(first <= high && (lli)a[first] * 2 < (lli)a[i]) { first++; } while(j <= high && a[j] <= a[i]) { temp[k] = a[j]; j++; k++; } ans += first - (mid + 1); temp[k] = a[i]; i++; k++; } while(j <= high){ temp[k] = a[j]; k++; j++; } k = 0; for(lli i = low; i <= high; i++){ a[i] = temp[k]; k++; } } void calc(vector <int> &a, lli low, lli high){ if(low >= high)return; lli mid = low + (high - low)/2; calc(a, low, mid); calc(a, mid + 1, high); merge(a, low, mid, high); } lli solve(vector<int> &A) { ans = 0; lli n = A.size(); calc(A, 0, n - 1); return ans; } int reversePairs(vector<int>& nums) { return solve(nums); } }; main(){ Solution ob; vector<int> v = {2,8,7,7,2}; cout << (ob.reversePairs(v)); }
ইনপুট
{2,8,7,7,2}
আউটপুট
3
