C++ এ বিপরীত জোড়া

ধরুন আমাদের একটি অ্যারে আছে, এই অ্যারেতে আমরা একটি জোড়া (A[i] এবং A[j]) কে গুরুত্বপূর্ণ বিপরীত জোড়া হিসাবে বলব যদি এটি নিম্নলিখিত শর্তগুলিকে সন্তুষ্ট করে -

• যদি i 2* সংখ্যা[j]

আমাদের গুরুত্বপূর্ণ বিপরীত জোড়ার সংখ্যা খুঁজে বের করতে হবে। সুতরাং ইনপুট যদি [2,8,7,7,2] এর মত হয়, তাহলে ফলাফল হবে 3।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• উত্তর :=0
• একটি ফাংশন মার্জ(), এটি একটি অ্যারে নেবে, নিম্ন, মধ্য, উচ্চ,
• k :=উচ্চ - নিম্ন + 1
• k আকারের একটি অ্যারের তাপমাত্রা সংজ্ঞায়িত করুন
• i :=নিম্ন, j =মধ্য + 1, k :=0
• প্রথম :=মধ্য + 1
• যখন i <=mid, do −
  • যখন প্রথমে <=উচ্চ এবং a[প্রথম] * 2
  • (প্রথমে ১ দ্বারা বাড়ান)
• যখন (j <=উচ্চ এবং a[j] <=a[i]), করো −
  • temp[k] :=a[j]
  • (j 1 দ্বারা বাড়ান)
  • (k 1 দ্বারা বাড়ান)
• উত্তর :=উত্তর + প্রথম - (মাঝ + 1)
• temp[k] :=a[i]
• (i 1 দ্বারা বাড়ান)
• (k 1 দ্বারা বাড়ান)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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