(归并排序求逆序对数)给定N(N<=10000)个互不相同的数,请计算出逆序对的数量。比如对于数列1、5、2、4、6,逆序对数量为2分别是(5,2)、(5,4)。
输入:
5
1 5 2 4 6
输出:
2
var
a:array[0..10000] of longint;
i,n,ans:longint;
procedure Merge(l,m,r:longint);
var
b:array[0..10000] of longint;
i,j,k:longint;
begin
i:=l;
j:=m+1;
k:=l;
while (i<=m) and (j<=r) do
if a[i]<a[j] then
begin
b[k]:=a[i];
i:=i+1;
k:=k+1;
end
else
begin
b[k]:=a[j];
j:=j+1;
k:=k+1;
ans:= ans+m-i+1 ;
end;
while i<=m do
begin
b[k]:=a[i];
i:=i+1;
inc(k) ;
end;
while j<=r do
begin
b[k]:=a[j];
inc(j) ;
k:=k+1;
end;
for i:=l to r do a[i]:=b[i] ;
end;
procedure MergeSort(l,r:longint);
var
m:longint;
begin
if l=r then exit;
m:=(l+r) div 2;
MergeSort(l,m);
MergeSort(m+1,r) ;
Merge(l,m,r);
end;
begin
read(n);
for i:=1 to n do read(a[i]);
ans:=0;
MergeSort(1,n);
writeln(ans);
end.