洛谷1093獎學金

題目

某國小打算為學習成績優秀的前5名學生發獎學金。每個學生都有3門課的成績:國文、數學、英語。先按總分從高到低排序，如果兩個同學總分相同，再按國文成績從高到低排序，如果兩個同學總分和國文成績都相同，那麼規定學号小的同學 排在前面，這樣，每個學生的排序是唯一确定的。

要求按排名順序輸出前五名名學生的學号和總分。

題解

多關鍵字排序：

第一關鍵字——總分

第二關鍵字——國文

第三關鍵字——學号

資料範圍： n<=300

時間複雜度O(n log n)

代碼

var
  i,j,n,x,y:longint;
  a,b,c:array[..]of longint;

procedure qsort(l,r:longint);
var
  i,j,key1,key2,key3,p,t:longint;
begin
  if l>=r then exit;
  i:=l;j:=r;
  p:=random(r-l+)+l;
  key1:=a[p];
  key2:=b[p];
  key3:=c[p];
  repeat
    while ( (a[i]>key1) or ((a[i]=key1)and(b[i]>key2))
            or ((a[i]=key1)and(b[i]=key2)and(c[i]<key3)))and(i<r) do inc(i);
    while ( (a[j]<key1) or ((a[j]=key1)and(b[j]<key2))
            or ((a[j]=key1)and(b[j]=key2)and(c[j]>key3)))and(j>l) do dec(j);
    if i<=j then
      begin
        t:=a[i];a[i]:=a[j];a[j]:=t;
        t:=b[i];b[i]:=b[j];b[j]:=t;
        t:=c[i];c[i]:=c[j];c[j]:=t;
        inc(i);dec(j);
      end;
  until i>j;
  qsort(i,r);
  qsort(l,j);
end;

begin
  readln(n);
  for i:= to n do
    begin
      readln(b[i],x,y);
      a[i]:=b[i]+x+y;
      c[i]:=i;
    end;
  randomize;
  qsort(,n);
  for i:= to  do
    writeln(c[i],' ',a[i]);
end.