UniLecs #Task. Стоимость арифметических операций

Published in

UniLecs

2 min readNov 17, 2019

Задача: определим следующую операцию: стоимость сложения двух чисел равна их сумме. Например, стоимость операции сложения числа 1 и 2 равна 3, как и их сумма. Дан набор чисел, необходимо сложить все числа с наименьшей стоимостью.

Входные данные: numbers[] — массив натуральных чисел не превосходящих 1000. Размер массива от 2 до 1000.

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

Пример:

Numbers[] = [ 1, 2, 3];

Output:

1й способ: 1 + 2 = 3 (Cost = 3); 3 + 3 = 6 (Cost = 6); Total Cost = 9;
2й способ: 1 + 3 = 4 (Cost = 4); 4 + 2 = 6 (Cost = 6); Total Cost = 10;
3й способ: 2 + 3 = 5 (Cost = 5); 1 + 5 = 6 (Cost = 6); Total Cost = 11;

Min Total Cost = 9;

Разбор

Ключ к решению — это на каждом шаге складывать 2 наименьших числа. Тогда суммарная стоимость сложения всего набора чисел будет наименьшей.
Получаем следующий алгоритм:

Сортируем входной набор чисел по возрастанию.
Запускаем цикл по этому набору: на каждом шаге будем брать два наименьших числа (два первых элемента набора, т.к. набор отсортирован), получаем их сумму. Удаляем эти числа из входного набора.
Сумму чисел добавляем в набор. Сортируем набор по возрастанию.
Считаем общую стоимость операций.
Выходим из цикла, когда в наборе останется один элемент. Это и будет итоговой стоимостью всех операций.

Примечание: некоторые языки программирования поддерживает такую структуру данных, как multiset — это контейнер, автоматически сортирует добавляемые элементы в порядке возрастания. Также multiset хранит повторяющееся элементы, в отличие от простого set.
Multiset позволит вам не выполнять сортировку вручную на каждом шаге цикла.

Подробнее почитать про эти структуры данных вы можете тут:
https://codelessons.ru/cplusplus/set-i-multiset-v-c-chto-eto-takoe-i-kak-s-nimi-rabotat.html