Соединение кабелей
Допустим, у вас есть
n кабелей с известными длинами, и вы хотите соединить их все в один большой кабель. Если вы соединяете два кабеля длиной x и y, то за это нужно заплатить x + y. После их объединения новый кабель будет иметь длину x + y.Задача: найти такую стратегию соединения, чтобы итоговые расходы — сумма всех плат за соединение — были как можно меньше.
Входные данные
Первая строка содержит одно целое число
n (1 ≤ n ≤ ) — количество кабелей.Следующая строка содержит разделённые пробелами целые числа (1 ≤ ≤ ), обозначающие длины кабелей.
Выходные данные
Программа должна вывести минимальную сумму, которую вы потратите, чтобы соединить все кабели.
Примеры
Входные данные | Выходные данные |
5
1 2 3 6 2 | 30 |
Пояснение
- Соединяем 1 и 2 ⇒ платим 3 ⇒ результат: 3 3 6 2
- Соединяем 2 и 3 ⇒ платим 5 ⇒ результат: 5 3 6
- Соединяем 3 и 5 ⇒ платим 8 ⇒ результат: 6 8
- Соединяем 6 и 8 ⇒ платим 14
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB