Lớp học có N học sinh, các học sinh được đánh số từ 1đến N. Học sinh i có chiều cao là Ai.Với mỗi học sinh i (i = 1,...,N), hãy đếm xem có bao nhiêu học sinh có chiều cao thấp hơn so với học sinh i.
Dữ liệu vào: Tệp văn bản HEIGHT.INP gổm:
+ Dòng đầu tiên ghi số nguyên N (1≤N≤105) là số học sinh trong lớp.
+ Dòng thứ hai ghi một dãy N số nguyên A1, A2, ...,AN (1≤ Ai≤109) - cho biết chiều cao của cáchọc sinh.
Kết quả: Ghi ra tệp văn bản HEIGHT.OUT N số nguyên, số thứ i cho biết số học sinh có chiều cao thấp hơn học sinh i.
Ví dụ: HEIGHT.INP: 4
1 3 2 4
HEIGHT.OUT : 0 2 1 3
uses crt; var a:array[0..2,0..100001] of longint; i,n:longint; f1,f2:text; procedure sort(l,r,key:longint); var i,j,x,t:longint; begin i:=l;j:=r;x:=a[key,(l+r) div 2]; repeat while a[key,i] < x do inc(i); while a[key,j] > x do dec(j); if i<=j then begin t:=a[1,i];a[1,i]:=a[1,j];a[1,j]:=t; t:=a[0,i];a[0,i]:=a[0,j];a[0,j]:=t; t:=a[2,i];a[2,i]:=a[2,j];a[2,j]:=t; inc(i);dec(j); end; until i>j; if l<j then sort(l,j,key); if i<r then sort(i,r,key); end; begin clrscr; assign(f1,'HEIGHT.INP');reset(f1); assign(f2,'HEIGHT.OUT');rewrite(f2); readln(f1,n); for i:=1 to n do begin read(f1,a[1,i]); a[0,i]:=i; end; sort(1,n,1); a[2,0]:=-1; for i:=1 to n do begin if a[1,i]>a[1,i-1] then a[2,i]:=i-1 else a[2,i]:=a[2,i-1]; end; sort(1,n,0); for i:=1 to n do write(f2,a[2,i],' '); close(f1);close(f2); readkey; end.