学步园

【题意】

给定n（n为奇数）个数，输出其中位数

【输入】

第一行为n

接下来n行分别为一个数

【输出】

这n个数的中位数

快排，输出中位数

program poj2388;
var
  n,i,j,k:longint;
  p:array [0..1000001] of longint;

procedure swap (var a,b:longint);
var
  i:longint;
begin
  i:=a;
  a:=b;
  b:=i;
end;

procedure qsort(s,e:longint);
var
  i,j,k:longint;
begin
  if s>=e then exit;
  i:=s;
  j:=e;
  k:=p[(s+e) div 2];
  while i<=j do
    begin
      while p[i]<k do inc(i);
      while p[j]>k do dec(j);
      if i>j then break;
      swap(p[i],p[j]);
      inc(i);
      dec(j);
    end;
  qsort(s,j);
  qsort(i,e);
end;

begin
  read(n);
  for i:=1 to n do
    read(p[i]);
  qsort(1,n);
  writeln(p[n-n div 2])
end.