Дистанционная подготовка: Пирамидальная сортировка
Пирамидальная сортировка
от Игорь Асямов - Пятница 4 Апрель 2008, 21:39
 

Здравстуйте!

Я сдал задачу "минимум на отрезке", но я не использовал св-ва пирамиды.

Но мне интересно как ее можно сдать, используя св-ва пирамиды? Вы не могли бы мне в этом помочь?

Re: Пирамидальная сортировка
от Роман Джабаров - Пятница 4 Апрель 2008, 23:32
 

заталкиваешь в priority_queue первые k элементов.

Я использовал pair<int,int> первое - значение, второе метка времени,т.е. шаг на котором элемент был добавлен в хип.

на каждом шаге вытаскиваешь из пирамиды элемент, если по метке времени элемент не подходит для текущего окна продолжаешь, если подходит - выводишь и опять заталкиваешь в хип.

Re: Пирамидальная сортировка
от Игорь Беляев - Суббота 5 Апрель 2008, 01:47
  А можно поинтересоваться как можно сделать эту задачку без использования свойства пирамиды?
Re: Пирамидальная сортировка
от Роман Джабаров - Суббота 5 Апрель 2008, 03:09
 

Исходя из ограничений на задачу легко видеть, что n**2 должно пройти ;)

best wishes

Re: Пирамидальная сортировка
от Игорь Асямов - Суббота 5 Апрель 2008, 12:50
 

Я просто использовал set! 

Re: Пирамидальная сортировка
от Роман Джабаров - Суббота 5 Апрель 2008, 12:54
 

а когда использовал set ты использовал его функционал по-мимо вытаскивания минимального элемента из начала?

Re: Пирамидальная сортировка
от Игорь Асямов - Суббота 5 Апрель 2008, 15:12
  Да, я использовал find.