C++의 역쌍

배열이 있다고 가정하고 이 배열에서 다음 조건을 충족하는 경우 한 쌍(A[i] 및 A[j])을 중요한 역 쌍으로 말할 것입니다. -

• i 2* nums[j]인 경우

중요한 역쌍의 수를 찾아야 합니다. 따라서 입력이 [2,8,7,7,2]와 같으면 결과는 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ans :=0
• merge() 함수를 정의하면 배열이 필요합니다(낮음, 중간, 높음)
• k :=높음 - 낮음 + 1
• k 크기의 어레이 온도 정의
• i :=낮음, j =중간 + 1, k :=0
• 첫 번째 :=중간 + 1
• i <=mid인 동안 −
  • 처음 <=high이고 a[first] * 2
  • (먼저 1씩 증가)
• 동안 (j <=high and a[j] <=a[i]), −
  • 온도[k] :=[j]
  • (j를 1씩 증가)
  • (k를 1씩 증가)
• ans :=ans + 첫 번째 - (중간 + 1)
• temp[k] :=[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