7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2011

Подразделы

Другие разделы

Дата и время

19/12/2024 20:45:46

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printРазбор задачи 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]);
loading