e-olymp 1228. Добавить все

Условие

Условие задачи отражает Вашу задачу: необходимо просто сложить числа. Но это будет унизительно если Вас попросят просто написать такую программу на языке C/C++ для заданного множества чисел. Давайте внесем в задачу оттенок изобретательности.

Введем понятие стоимости для операции сложения. Стоимость сложения двух чисел положим равным их сумме. Например, сложить числа $1$ и $10$ стоит $11$. Стоимость сложения $1,2$ равна $3$. Складывать числа можно разными способами:

  1. $1 + 2 = 3$ (стоимость = 3), $3 + 3 = 6$ (стоимость = 6), Всего = 9
  2. $1 + 3 = 4$ (стоимость = 4), $2 + 4 = 6$ (стоимость = 6), Всего = 10
  3. $2 + 3 = 5$ (стоимость = 5), $1 + 5 = 6$ (стоимость = 6), Всего = 11

Надеемся, Вы поняли Вашу задачу. Вам необходимо сложить все числа так, чтобы суммарная стоимость их сложения была наименьшая.

Входные данные

Начинаются целым числом $n (2 \leq n \leq 100000)$, за которым следуют $n$ целых неотрицательных чисел (все числа меньше $100000$).

Выходные данные

Вывести наименьшую стоимость сложения всех чисел.

Тесты

Входные данные Выходные данные
$4$
$10$ $12$ $13$ $11$
$92$
$5$
$100$ $11$ $8$ $30$ $12$
$272$
$4$
$2$ $2$ $2$ $2$
$16$
$6$
$1$ $2$ $3$ $4$ $5$ $6$
$51$

Код решения

Решение

Стоимость сложения всех чисел будет минимальной, если на каждом следующем шаге мы будем складывать два наименьшие числа из множества $A$, состоящего из данного ряда чисел и уже вычисленных «частичных сумм». Таким образом, каждый шаг цикла поиска минимальной стоимости сложения будет состоять из нахождения двух минимальных чисел из множества, удаления этих чисел из множества $A$ и добавления в него результата их суммирования. В специальную переменную $minSum$ будем также каждый раз добавлять результат этого суммирования. Таким образом, количество элементов во множестве будет с каждым шагом уменьшаться на одно, и в конце, когда в нем останется единственный элемент, переменная $minSum$ будет содержать искомую стоимость сложения всех чисел.
Реализовать такой код достаточно просто, если реализовать множество $A$ в виде очереди с приоритетом.

Ссылки

Условие задачи на e-olymp.com
Код решения на ideone.com

Добавить комментарий

Ваш адрес email не будет опубликован.