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.