10954. Сложить все

Стоимость сложения двух чисел равна их сумме. То есть для того чтобы к 1 прибавить 10, следует заплатить 11. В задаче требуется сложить все заданные числа, потратив при этом наименьшее количество денег.

Например, складывать числа 1, 2 и 3 можно одним из трех способов:

1 + 2 = 3, стоимость 3 3 + 3 = 6, стоимость 6 Общая стоимость 9

1 + 3 = 4, стоимость 4 4 + 2 = 6, стоимость 6 Общая стоимость 10

2 + 3 = 5, стоимость 5 1 + 5 = 6, стоимость 6 Общая стоимость 11

Первый способ сложения самый дешевый.

Вход. Первая строка каждого теста содержит количество складываемых чисел n (2 £ n £ 500). Вторая строка теста содержит n чисел, каждое из которых не более 100000. Последняя строка содержит n = 0 и не обрабатывается.

Выход. Для каждого теста найти наименьшую стоимость, за которую можно сложить все заданные n чисел.

Пример входа

3

1 2 3

4

1 2 3 4

0

Пример выхода

9

19

РЕШЕНИЕ

жадный алгоритм

Анализ алгоритма

Каждый раз следует складывать два наименьших числа. Тогда суммарная стоимость сложения всех n чисел будет наименьшей.

Реализация алгоритма

Входные числа храним в мультимножестве s (числа могут повторяться). Два наименьшие числа всегда находятся в начале мультимножества.

multiset<int> s;

Читаем количество чисел n. Вводим последовательность слагаемых и заносим их в мультимножество s.

while(scanf("%d",&n),n)

{

s.clear();

for(i = 0; i < n; i++)

scanf("%d",&num),s.insert(num);

В переменной res накапливаем стоимость сложений. Пока не осталось одно число (размер мультимножества s больше 1), складываем два наименьших числа и заносим их сумму в s. Стоимость сложения чисел a и b равно a + b.

res = 0;

while(s.size() > 1)

{

a = *s.begin(); s.erase(s.begin());

b = *s.begin(); s.erase(s.begin());

s.insert(a + b);

res += a + b;

}

Когда в мультимножестве останется одно число, выводим ответ – значение переменной res.

printf("%d\n",res);

}