POJ 1804（最小相邻数移动）
题目大意：对乱序列相邻2数移动，使得用最小步数使其有序
解法：归并排序
定理：
一个乱序序列的逆序数 = 在只允许相邻两个元素交换的条件下,得到有序序列的交换次数
Program P1804;const maxn=1000;Var tt,i,j,k,n,ans:longint; a,le,re:array[1..maxn] of longint;procedure mergesort(l,r:longint);var i,j,k,mid:longint;begin if l=r then exit; mid:=(l+r) shr 1; mergesort(l,mid); mergesort(mid+1,r); for i:=l to mid do le[i-l+1]:=a[i]; le[mid+2-l]:=maxlongint; for i:=mid+1 to r do re[i-mid]:=a[i]; re[r+1-mid]:=maxlongint; i:=1;j:=1; for k:=l to r do begin if (le[i]<=re[j]) then begin a[k]:=le[i]; inc(i); end else begin a[k]:=re[j]; inc(j); inc(ans,mid-l+1-(i-1)); end; end;end;Begin readln(tt); for k:=1 to tt do begin writeln('Scenario #',k,':'); read(n); for i:=1 to n do read(a[i]); ans:=0; mergesort(1,n); writeln(ans); writeln; end;end.