SGU 114 — Telecasting station
水题.求出中位数即可.
根据WindyWinter的blog,有两点注意.
Pascal注意,读入n对数时,应该用read而不是readln,因为虽然样例数据有换行,但题目中的描述是没有换行的.否则会像我一样WA on 14.
C++注意,iostream会TLE on 12.
{
SGU 114; Telecasting station
- sqybi’s code
}
//for my winsty
program sgu114_sqybi;
const
nn = 15000;
type
rec = record
p, v: longint;
end;
var
s, t, n, i: longint;
a: array[1..nn]of rec;
procedure qsort(l, r: longint);
var
i, j, d: longint;
t: rec;
begin
if l >= r then exit;
i := l;
j := r;
d := a[(l+r) div 2].p;
repeat
while a[i].p < d do inc(i);
while a[j].p > d do dec(j);
if i <= j then begin
t := a[i];
a[i] := a[j];
a[j] := t;
inc(i);
dec(j);
end;
until i > j;
qsort(l, j);
qsort(i, r);
end;
begin
readln(n);
s := 0;
for i:=1 to n do begin
read(a[i].p, a[i].v);
s := s + a[i].v;
end;
s := s div 2 + 1;
qsort(1, n);
i := 0;
t := 0;
while t < s do begin
i := i + 1;
t := t + a[i].v;
end;
writeln(a[i].p, ‘.00000′);
end.
阅读(82 次)