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

Question

对于那些不了解反转的人。

反转-

给定一个包含 N 个整数的数组 A，该数组的反转被定义为任何满足 i < j 且 A[i] > A[j] 的索引对 (i,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 代表第二个数组，B 部分。

如果 X 被复制到输出数组(即如果 X < Y) - 那么我们就没有反转。

否则如果 Y 被复制到输出数组(即如果 X > Y)。 然后我们有反转计数 = 计数 + mid - 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 链接 - 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