重做后的新感悟
在归并排序的思想上分为两半
从小到大,如果左半边a[i]>a[j],说明a[i]可以与a[mid+1,j]构成逆序
这是我重做后的错误思路,正确的思路后是当a[i]>a[j],a[i,mid]都可以与a[j]构成逆序
看起来蛮符合,但是提交错误,我对比后yxc做的后模拟一个样例后发现原因
以a[i]={2,16,71,72,88},a[j]={38,50,64,72,94}为例
i
2 16 71 72 88
j
38 50 64 72 94
开始 a[i]<a[j]一直到i=71,
i
2 16 71 72 88
j
38 50 64 72 94
这时a[i]>a[j],j++,res+=(j-mid)={71,38}
i
2 16 71 72 88
j
38 50 64 72 94,这时a[i]>a[j],j++,res+=(j-mid)={71,38}+{71,38}+{71,50}
按这个思路res中会有重复的逆序对
#include<iostream>
using namespace std;
const int N=100010;
typedef long long LL;
int a[N],temp[N];
int n;LL res=0;
LL merge(int l,int r)
{
if(l>=r)return 0;
int mid=(l+r)>>1;
res=merge(l,mid)+merge(mid+1,r);
int i=l,j=mid+1,k=0,sum=0;
while(i<=mid&&j<=r)
{
if(a[i]>a[j])
{
res+=mid-i+1;
temp[k++]=a[j++];
}
else
temp[k++]=a[i++];
}
//cout<<"---"<<sum<<"---"<<endl;
//cout<<res<<endl;
while(i<=mid)temp[k++]=a[i++];
while(j<=r)temp[k++]=a[j++];
for(i=l,j=0;i<=r;++i,++j)
a[i]=temp[j];
return res;
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
merge(1,n);
cout<<res;
return 0;
}