Контест Middle Куча спрашивают часто обновлено
Медиана потока: сумма медиан
Условие
Числа приходят по одному. После прихода каждого числа нужно знать нижнюю медиану всех полученных: если их t, это элемент с номером ⌈t/2⌉ в отсортированном порядке (для 4 чисел второй, для 5 третий). Выведите сумму этих n медиан.
Ввод: в первой строке n (1 ≤ n ≤ 2500), во второй n чисел (0 ≤ aᵢ ≤ 10⁹) в порядке поступления.
Вывод: сумма медиан (может не поместиться в 32 бита).
Пример 1
Ввод:
5
5 15 1 3 8
Вывод:
23
Пример 2
Ввод:
1
7
Вывод:
7
Как подойти
Подсказки: 2
- Разделите полученные числа на две половины.
- Меньшая половина в max-куче, большая в min-куче, размеры отличаются не больше чем на 1.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.