Начало
Соревнования
Разбор задачи G. Шпаги
Тема: быстрая сортировка, бинарное деревоСложность: средняя
Сначала нужно отсортировать шпаги в порядке убывания их возраста.
type info=
record
age:integer; { возраст }
ind:integer; { номер шпаги в исходной последовательности }
end;
var o:array[1..100000] of info;
t:info;
p:array[1..100000] of integer;
ai,n,k,i:integer;
procedure qsort(l,r:integer);
var i,j,m:integer;
begin
if l>=r then exit;
m:=o[l+random(r-l+1)].age;
i:=l;
j:=r;
while i<=j do
begin
while o[i].age>m do inc (i);
while o[j].age<m do dec (j);
if i<=j then
begin
t:=o[i];o[i]:=o[j];o[j]:=t;
inc(i); dec(j);
end;
end;
qsort(l,j);
qsort(i,r);
end;
begin
read(n,k);
for i:=1 to n do
begin
read(ai);
o[i].age:=ai;
o[i].ind:=i;
end;
qsort(1,n);
...
end.
Пояснения к алгоритму быстрой сортировки можно посмотреть в разборе задачи 50. Закраска прямой. Здесь этот алгоритм модифицирован, чтобы сортировать значения по убыванию.
Затем нужно использовать одно из представлений бинарного дерева. Элементы бинарного дерева хранятся в массиве, при этом `i`-й элемент содержит узел дерева, а элементы с номерами `2*i` и `2*i+1` содержат два потомков этого узла. Соответственно, для `i`-го элемента предком будет элемент с номером `⌊i/2⌋`.
Для построения дерева копирования используем жадный алгоритм и будем рассматривать копии шпаг в порядке убывания возраста и цеплять их в качестве потомков к свободным веткам узлов, соответствующих шпагам наибольшего возраста из возможных.
Любой другой способ приведет к уменьшению максимума разницы в возрасте между шпагами и их копиями.
Заполнение уровней бинарного дерева будет идти последовательно, в порядке убывания возраста шпаг. Фактически после сортировки элементы в массиве уже образуют такое дерево. Остается только проверить, что для всех `i` от 2 до `n` выполняется `"age"_{i/2}-"age"_i\ ≥\ k`.
p[o[1].ind]:=0; { у самой старой шпаги нет предка }
for i:=2 to n do
begin
if o[i div 2].age-o[i].age<k then
begin { неудача }
writeln(-1);
halt;
end;
p[o[i].ind]:=o[i div 2].ind;
end;
{ выводим ответ }
for i:=1 to n do
write(' ',p[i]);
