记录编号	19602	评测结果	AAAAAAAAAA
题目名称	排序工作量	最终得分	100
用户昵称	mouse	是否通过	通过
代码语言	Pascal	运行时间	0.053 s
提交时间	2010-10-13 15:32:00	内存使用	0.27 MiB

program pxgzl;
Const
  Max=10000;				{数组界限}
Type
   Zis=array[1..max] of real;		{数组类型说明}

Var
   Tot:longint;				    {“逆序对”总数}
   N:integer;						{数组大小}
   a,b:zis;					{记录数列的数组}
   F:Text;						{文件变量说明}

  Procedure Init;					{初始化过程，输入数据}
  Var
    i:longint;
    Begin
      Assign(f,'sortt.in');
      Reset(f);
      Readln(f,n);
      For i:=1 to n do
          read(f,a[i]);
      Close(f);
    end;

   Procedure Sort(L,R:integer);		{利用归并排序求“逆序对”}
     Var
       T:integer;
          Procedure Merge(l,t,r:longint);
		   {将两个排好序的数组“归并”在一起，同时求出左部分相对于右部分“逆序对”的数目}
          Var
            i,j,k:longint;
            Begin
              i:=l;
              j:=T+1;
              k:=l-1;
              While (i<=t) and (j<=r) do
                Begin
                  if a[i]<a[j] then
                    Begin
                      inc(k);
                      b[k]:=a[i];
                      inc(i);
                    end
                  Else
                    Begin
                      inc(k);
                      b[k]:=a[j];
                      inc(tot,t-i+1);
                      inc(j);
                    end;
                end;

              while i<=t do		{剩余部分的尾处理}
                Begin
                  inc(k);
                  b[k]:=a[i];
                  inc(i);
                end;
              while j<=r do
               Begin
                 inc(k);
                 b[k]:=a[j];
                 inc(j);
               end;

              for i:=l to r do a[i]:=b[i];{返回两个数组的归并后的排序数组}
            end;
        Begin
          if l<r then
           Begin
             t:=(l+r) div 2;		{“分”}
             Sort(l,t);			{“分”部分“治”}
             Sort(t+1,r);
             Merge(l,t,r);		{“合”}
           end;
        end;

 Procedure Print;			{输出结果}
   Begin
     Assign(f,'sortt.out');
     rewrite(f);
       Writeln(f,tot);
     Close(f);
   end;

Begin				{主过程}
  Init;					{输入数据}
  Tot:=0;
  Sort(1,n);				{求解}
  Print;					{输出结果}
end.