POJ 1007(求逆序对数)

内容目录

求逆序对数,2关键字排序

Program P1007;
var
   n,m,i,j,k,l,p:longint;
   a:array[1..200] of string;
   s:string;
   b,num:array[1..200] of longint;
function h(s:string):longint;
var
   i,j,a,c,g,t:longint;
begin
   a:=0;
   c:=0;
   g:=0;
   t:=0;
   h:=0;
   for i:=length(s) downto 1 do
   begin
      if s[i]='A' then inc(a);
      if s[i]='C' then
      begin
         inc(c);
         inc(h,a);
      end;
      if s[i]='G' then
      begin
         inc(g);
         inc(h,a+c);
      end;
      if s[i]='T' then
      begin
         inc(t);
         inc(h,a+c+g);
      end;
   end;
end;
procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
   s2:string;
begin
   i:=l;
   j:=r;
   m:=b[(l+r) div 2];
   repeat
      while b[i]<m do inc(i);
      while b[j]>m do dec(j);
      if i<=j then
      begin
         p:=b[i];
         b[i]:=b[j];
         b[j]:=p;
         p:=num[i];
         num[i]:=num[j];
         num[j]:=p;
{         s2:=a[i];
         a[i]:=a[j];
         a[j]:=s2;
}        inc(i);
         dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);
end;
begin
   readln(n,m);
   for i:=1 to m do
   begin
      readln(a[i]);
      b[i]:=h(a[i]);
      num[i]:=i;
   end;
   qsort(1,m);
   i:=1;
   while (i<m) do
   begin
      if b[i]<b[i+1] then inc(i)
      else
      begin
         for j:=i+1 to m do if b[j]<>b[i] then break;
         if (b[i]<>b[m]) then dec(J);
         for k:=i to j-1 do
            for l:=k+1 to j do
               if num[k]>num[l] then
               begin
                  p:=num[k];
                  num[k]:=num[l];
                  num[l]:=p;
 {                 s:=a[k];
                  a[k]:=a[l];
                  a[l]:=s;
  }             end;
         i:=j+1;
      end;
   end;
   for i:=1 to m do writeln(a[num[i]]);
end.