Несложная задача на структуры данных, но с некоторыми подводными камнями, которые могут помочь избегать ошибок в будущем. Читаем условие:
Уже из приведённого примера следует, что надо складывать два самых маленьких числа. Это же следует и из логики: если большое число участвует в нескольких операциях сложения, то в каждой из них за это число надо будет заплатить. То есть надо стараться чаще использовать маленькие числа (ведь количество операций сложения всегда будет равно N - 1).
Отсюда получаем, что нам необходимо поддерживать упорядоченный набор чисел, из которого легко доставать минимальное и в который легко класть сумму.
При ограничении N до 100000 поддерживать сортированный массив очень накладно по времени. Однако существует целое множество структур данных, с помощью которым можно это реализовать: куча и всевозможные деревья поиска.
Одним из самых простых вариантов является использование имеющейся в стандартной библиотеке шаблонов структуры set (а точнее multiset, так как числа в входных данных могут повторяться). Они как реализованы в виде красно-чёрного бинарного дерева поиска, то есть хранят элементы в упорядоченном виде и позволяют выполнять операции удаления и вставки за логарифмическое время.
Начнём как обычно с подключения библиотек:
Здесь вместо традиционной iostream я выбрал cstdio, чтобы использовать форматированный вывод, так как требуется вывести ровно два знака после запятой. А смешивать различные библиотеки ввода и вывода в одной задаче - не очень хорошая идея.
Это немного снижает удобство считывания данных, но их не так много, поэтому ничего страшного:
Теперь все числа лежат в multiset'е, и мы можем приступить к суммированию:
Цикл можно было бы написать и for, так как мы заранее знаем количество итераций. А вот тип данных для переменной sum надо выбирать осознанно, так как сумма легко может выйти за пределы int'а.
Теперь напишем функцию, которая достаёт минимальный элемент из множества (и удаляет его):
Минимальный элемент всегда лежит в начале, поэтому получить его значение можно через разыменование итератора. Но удалить значение просто так нельзя, так как у нас multiset, и при удалении исчезнут все числа с данным значением. Однако, если в метод erase передать итератор, то удалится только данных элемент.
iterator erase (const_iterator position);
size_type erase (const value_type& val);
Во втором случае возвращается число удалённых элементов. Помимо прочего удаление через передачу позиции удаляемого элемента работает амортизировано за константное время (а не за логарифмическое). Однако в нашем случае амортизированные оценки не подходят, потому что помимо удаления есть и добавления во множество.
Теперь дважды вызовем написанную функцию, найдём сумму и добавим её в общее множество:
Замечу, что нет необходимости каждый раз вычислять 5% от складываемых чисел, достаточно сделать это в самом конце. Что мы и сделаем при выводе:
Именно для функции printf мы и подключали библиотеку cstdio, чтобы удобно задать формат вывода вещественного числа.
Предыдущий выпуск: Задача 396. Точки и отрезки
А ещё проходит небольшой опрос, чтобы сделать канал лучше.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
