题目描述
题目给出的方法其实是逆序对的逆向算法,如果对归并不了解就没办法用归并的算法算
即新加数字的移动位置之和本质上是求其存在的逆序对之和
归并求逆序对算法
归并前先二分,变成最小无序组合。
然后再并,当后序列有数字小于前序列时,前序列小于该数字的最小数字的后面位置的数量即其逆序对数量。
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,a[121012],temp[121012];
long long ans;
void msort(int l,int r){
if(l==r)return;
int m=(l+r)/2;
msort(l,m);
msort(m+1,r);
int k=l,i=l,j=m+1;
for(;k<=r;k++){
if(i<=m&&(j>r||a[i]<=a[j]))
temp[k]=a[i++];
else{
ans=ans+m-i+1;
temp[k]=a[j++];
}
}
for(i=l;i<=r;i++)
a[i]=temp[i];
}
int main(){
while(1){
scanf("%d",&n);
if(!n)
break;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
msort(1,n);
printf("%lld\n",ans);
ans=0;}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla