Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Heap
Задача Bicycle

 

Задача Heap. «Купою» будемо називати неспадну послідовність з двох або більше чисел. «Висотою купи» будемо називати самий більший елемент послідовності. «Купковим розподілом» послідовності назвемо набір з мінімальної кількості «куп», таких,  що коли їх записати по черзі зліва направо, отримаємо початкову послідовність. Вам дано набір чисел. Утворіть таку послідовність, щоб сума "висот куп" була максимальна. Послідовність можна отримувати з початкового набору довільною перестановкою початкового набору.

Технічні умови.   Програма Heap  читає з стандартного введення (клавіатури) число N (2 ≤ N ≤ 100000)) – кількість чисел у наборі, а далі N цілих чисел кожне в межах від 1 до 100000. Числа розділено пропусками. Програма виводить на пристрій стандартного виведення (екран) єдине число – максимально можливу суму «висот куп» в послідовності.

Приклад

Введення                   Виведення

4 1 2 3 4                        7


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"