求解逆序数
方法一：（直接求解法，时间复杂度为0(N^2)）
#include<cstdio>
#include<iostream>
using namespace std;
#define MAX 10000
#define N 500
int a[N];
int nixu(int a[],int n)
{
int i,j;
int count=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
count++;
}
}
return count;
}
int main()
{
int n;
while(1)
{
cin>>n;
if(!n)
break;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<nixu(a,n)<<endl;
}
return 0;
}
#include<iostream>
using namespace std;
#define MAX 10000
#define N 500
int a[N];
int nixu(int a[],int n)
{
int i,j;
int count=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
count++;
}
}
return count;
}
int main()
{
int n;
while(1)
{
cin>>n;
if(!n)
break;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<nixu(a,n)<<endl;
}
return 0;
}
方法二：（分治法，时间复杂度为O(NlogN)）
#include<cstdio>
#include<iostream>
using namespace std;
#define MAX 10000
#define N 500
long a[N],b[N],c[N];
#include<iostream>
using namespace std;
#define MAX 10000
#define N 500
long a[N],b[N],c[N];
//合并两部分的逆序数，并进行排序
long Merge(int p,int q,int r)
{
long cnt=0;
for(int i=p;i<=q;i++)
b[i]=a[i];
for(int j=q+1;j<=r;j++)
c[j]=a[j];
b[q+1]=c[r+1]=MAX;
int bb=p,cc=q+1;
for(int k=p;k<=r;k++)
{
if(b[bb]<=c[cc])
{
a[k]=b[bb++];
}
else
{
a[k]=c[cc++];
cnt+=q+1-bb;
}
}
return cnt;
}
//分治法，求解每一部分的逆序数
long MergeSort(int p,int r)
{
long cnt=0;
if(p==r)
return 0;
int q=(p+r)/2;
cnt+=MergeSort(p,q);
cnt+=MergeSort(q+1,r);
cnt+=Merge(p,q,r);
return cnt;
}
int main()
{
int n;
while(1)
{
cin>>n;
if(!n)
break;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<MergeSort(0,n-1)<<endl;
}
return 0;
}