数组中反转计数的数量。使用归并排序

Question

对于那些不知道反转的人。

反转-

给定一个包含 N 个整数的数组 A，该数组的反转定义为任何一对索引 (i,j) 使得 i < j 且 A[i] > A[j]。

简而言之：

{inv}(A) = {(A(i),A(j)), i < j { and } A(i) > A(j)}

例如，数组 a={2,3,1,5,4} 有三个反转：(1,3), (2,3), (4,5)，对于条目对(2,1), (3,1), (5,4).

总反转计数 = 3。

好吧，我试图通过使用标准归并排序来解决这个问题。这是我认为它的工作原理。

假设在某个阶段，合并排序的 partA 和 partb 是

A 部分- [1,2,3].

B 部分- [4,5]

现在，设 X 为第一个数组 partA 的元素。 Y 用于第二个数组，partB.

如果 X 被复制到输出数组（即如果 X < Y）——那么我们没有反转。

否则如果 Y 被复制到输出数组（即如果 X > Y）。然后我们有反转计数 = 计数 + 中 - i+1。（我是那个元素的位置）。由于是升序排列，位置j>i的所有元素，X[j]>Y.

这里是代码的更多细节。

#include <iostream>
#include <vector>
using namespace std;

vector<int> a;
vector<int> c;
void merge(int low, int high, int mid);
void mergesort(int low, int high)
{
 int mid;
 if (low < high)
 {
     mid=(low+high)/2;
     mergesort(low,mid);
     mergesort(mid+1,high);
     merge(low,high,mid);
 }
return ;
}

int count ; //to store the inversion count
void merge(int low, int high, int mid)
{
int i, j, k;
i = low;
k = low;
j = mid + 1;
// standard merging from merge sort
while (i <= mid && j <= high)
{
    if (a[i] < a[j])
    {
        c[k] = a[i];
        k++;
        i++;
    }
    else
    {
        c[k] = a[j];
        k++;
         j++;
      //   cout<<a[i]<<" "<<mid<<" "<<i<<"\n";
         count += mid - i+1; // This is where the trick occurs, if X > Y,
         //eg. in [3, 4, 5] and [1,2]
         //if(3>1) then 4,5 is obviously greater then 1, thus making count as mid - i+1              
     }
 }
while (i <= mid)
{
    c[k] = a[i];
    k++;
    i++;
}
while (j <= high)
{
    c[k] = a[j];
    k++;
    j++;
}
for (i = low; i < k; i++)
{
    a[i] = c[i];
 }
}
int main()
{
//int a[20], i, b[20];
int T;
cin>>T;
while(T--){
    //cout<<"enter  the elements\n";
    int N;
    cin>>N;
    count =0;
    a.clear(); a.resize(N);
    c.clear(); c.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin>>a[i];
    }
    mergesort(0, N-1);

    cout<<count<<"\n";
}
}

好的，现在我开始怀疑了，我相信上面实现的逻辑足以解决反转的数量，但由于某些奇怪的原因，它不是，我不确定是什么导致了这里的 WA。

我卡在这个问题上有一段时间了，想不通。这不是作业问题，只是我看不出逻辑有问题，代码仍然不起作用，可能的原因是什么？求助！

Ideone Link - https://ideone.com/nmvl7i

关于 Spoj 的问题 - http://www.spoj.com/problems/INVCNT/

注意：前两个测试用例工作正常，提交时我得到了 WA。

Answer 1

你的解决方案的问题是结果可能大于整数范围，例如，如果序列为n，n - 1，...，1，（非递增）反转的次数将是n*(n - 1)/2 和 n = 2*10^5，结果将比整数范围大得多。

因此，将 int count 更改为 long long count 和

更改此行：

count += mid - i + 1;

进入：

count += (long long)mid - (long long) i + 1L;

你会得到被接受的答案。

我的accepted code

数组中反转计数的数量。使用归并排序

Number of Inversion Count in an array. Using Merge Sort

c++

algorithm

mergesort