输入样例:
在这里给出一组输入。例如:
6
-42 23 6 28 -100 65537
结尾无空行
输出样例:
在这里给出相应的输出。例如:
5
结尾无空行
解答:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
int a[MAXN];
int b[MAXN];
int l,r,k;
int ans=0;
int Merge(int low,int mid,int high)
{
l=low;r=mid+1;k=low;
while(l<=mid&&r<=high)
{
if(a[l]>a[r])
{
b[k++]=a[r++];
ans+= (mid-l+1);
}
else b[k++]=a[l++];
}
while(l<=mid) b[k++]=a[l++];
while(r<=high) b[k++]=a[r++];
for(int i=low;i<=high;i++)
{
a[i]=b[i];
}
}
int mergesort(int low,int high)
{
if(low>=high) return 0;
int mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
Merge(low,mid,high);
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
mergesort(0,n-1);
cout<<ans;
return 0;
}