C++ में रिवर्स पेयर्स समस्या

मान लीजिए हमारे पास एक ऐरे है, इस ऐरे में हम एक पेयर (A[i] और A[j]) को महत्वपूर्ण रिवर्स पेयर कहेंगे यदि यह निम्नलिखित शर्त को संतुष्ट करता है:

• यदि i < j और A[i] > 2 * A[j]

हमें महत्वपूर्ण रिवर्स पेयर्स की संख्या ढूंढनी है। यदि इनपुट [2,8,7,7,2] है, तो परिणाम 3 होगा।

समाधान दृष्टिकोण (मर्ज सॉर्ट आधारित)

हम मर्ज सॉर्ट का उपयोग करके रिवर्स पेयर्स गिन सकते हैं। मर्ज चरण के दौरान, हम गिनते हैं कि बाएं आधे में कितने एलिमेंट्स दाएं आधे के एलिमेंट्स के दोगुने से अधिक हैं।

1. ans := 0
2. merge() फंक्शन परिभाषित करें जो लेता है: ऐरे a, low, mid, high।
   • अस्थायी ऐरे temp बनाएं।
   • i := low, j := mid + 1, k := 0
   • first := mid + 1
   • i <= mid तक लूप:
     • first <= high और a[first] * 2 < a[i] तक first बढ़ाएं।
     • j <= high और a[j] <= a[i] तक मर्ज करें।
     • ans += first - (mid + 1)
     • temp[k] = a[i], i++, k++
   • शेष एलिमेंट्स कॉपी करें।
   • temp को वापस a में कॉपी करें।
3. calc() फंक्शन परिभाषित करें जो रिकर्सिवली calc(a, low, mid), calc(a, mid+1, high), फिर merge(a, low, mid, high) कॉल करता है।
4. solve() फंक्शन ans=0 सेट करता है, calc(A, 0, n-1) कॉल करता है, ans लौटाता है।

C++ कार्यान्वयन

#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);
    }
};

int main() {
    Solution ob;
    vector<int> v = {2, 8, 7, 7, 2};
    cout << ob.reversePairs(v);
    return 0;
}

इनपुट

{2,8,7,7,2}

आउटपुट

3