我写的代码如下:
include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
bool cmp1(int a,int b)
{
return a<b;
}
int Snum(int a[],int left,int right)
{
if(left==right)return 0;
else if(right==left+1)
{
if(a[left]<a[right])return 1;
elsereturn 0;
}//递归出口
int b[100050];
for(int i=left;i<=right;i++)
{
b[i]=a[i];//将a赋值给临时数组b
}
int mid=left+(right-left)/2;
sort(b+left,b+mid+1,cmp1);
sort(b+mid+1,b+right+1,cmp1);
queue<int> l,r;
for(int i=left;i<=mid;i++)
{
l.push(b[i]);
}
for(int i=mid+1;i<=right;i++)
{
r.push(b[i]);//将排序好的数组赋值给队列l,r
}
int count=0;
while(!l.empty()&&!r.empty())
{
if (l.front()<r.front())
{
l.pop();
count+=r.size();
}
elser.pop();
}
return count+Snum(a,left,mid)+Snum(a,mid+1,right);
}
int main()
{
int N;
cin>>N;
int a[N+1];
for(int i=0;i<N;i++)
{
cin>>a[i];
}
cout<<Snum(a,0,N-1)<<endl;
return 0;
}