Здравствуйте.
Прошу прощения за орфографические ошибки, допущенные в прошлом выпуске.
Ко мне пришло письмо с очень дельными советами от Рафаила Ахмедишева.
В частности, он предложил несколько задач с acm.timus.ru,
которые можно решить используя полученные в рассылке знания. Я предлагаю
Вам решить одну из них.
Задача
Описание задачи
Рассмотрим последовательность N положительных целых чисел. Если N нечётно,
медианой такой последовательности будем называть число, которое окажется
в середине этой последовательности после её сортировки. Легко заметить,
что если нумерация элементов начинается с 1, то медиана занимает позицию
(N+1)/2 в отсортированной последовательности. Если же N нечётно, то медианой
последовательности назовём полусумму двух «средних» элементов, т.е. элементов,
занимающих позиции N/2 и (N/2)+1 в отсортированной последовательности.
Требуется написать программу, которая находила бы медиану последовательности. Входные данные
В первой строке входного файла записано число N (1 <= N <= 250000).
В последующих N строках перечислены элементы последовательности (по одному
числу на строке). Каждый элемент последовательности – положительное целое
число, не превышающее 2^32-1. Выходные данные
Требуется вывести медиану последовательности, содержащейся во входном
файле. Пример входных данных
4
3
6
4
5 Пример выходных данных
4.5 Ограничения
Решение должно работать не больше секунды.
Решение должно использовать не больше 1000 Кб памяти.
Решение не может использовать файлы в качестве дополнительной памяти. Дополнительно
Условие задачи можно найти здесь: http://acm.timus.ru/problem.aspx?space=1&num=1306.
Там же можно проверить своё решение.
Вопросы связанные с задачей прошу направлять Рафаилу
Ахмедишеву.
Если Вы получите AC, то "Время работы" и "Выделено памяти"
прошу отослать мне.
Немножко теории.
Пирамиду выгодно использовать для построения очереди
по приоритету. Почему? Потому что элемент с максимальным приоритетом всегда
находится в вершине пирамиды. В прошлый раз мы не рассмотрели операцию
добавления элемента. Для того чтобы добавить элемент в пирамиду, надо дописать
его в конец массива и применить к нему алгоритм пузырькового подъёма.
Суть алгоритма понятна из названия. Вот его реализация.
procedure HeapUp(_Ind : integer);
var
ParentInd, StartValue : integer;
begin
StartValue:=a[_Ind];
ParentInd:=(_Ind-1) div 2;
while (_Ind > 0) and (StartValue > a[ParentInd]) dobegin
a[_Ind]:=a[ParentInd];
_Ind:=ParentInd;
ParentInd:=(_Ind-1) div 2;
end;
a[_Ind]:=StartValue;
end;
