Условие
Условие задачи отражает Вашу задачу: необходимо просто сложить числа. Но это будет унизительно если Вас попросят просто написать такую программу на языке C/C++ для заданного множества чисел. Давайте внесем в задачу оттенок изобретательности.
Введем понятие стоимости для операции сложения. Стоимость сложения двух чисел положим равным их сумме. Например, сложить числа $1$ и $10$ стоит $11$. Стоимость сложения $1,2$ равна $3$. Складывать числа можно разными способами:
- $1 + 2 = 3$ (стоимость = 3), $3 + 3 = 6$ (стоимость = 6), Всего = 9
- $1 + 3 = 4$ (стоимость = 4), $2 + 4 = 6$ (стоимость = 6), Всего = 10
- $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$ |
Код решения
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import java.util.PriorityQueue; import java.util.Scanner; public class Main{ public static void main(String[] args) { PriorityQueue<Long> nums = new PriorityQueue<Long>(); Scanner sc = new Scanner(System.in); long n = sc.nextLong(); for (int i = 0; i < n; i++) { long number = sc.nextLong(); nums.add(number); } long minSum = 0; long a; long b; while (!nums.isEmpty()) { a = nums.poll(); if (nums.isEmpty()) { break; } b = nums.poll(); minSum += a + b; nums.add(a + b); } System.out.println(minSum); } } |
Решение
Стоимость сложения всех чисел будет минимальной, если на каждом следующем шаге мы будем складывать два наименьшие числа из множества $A$, состоящего из данного ряда чисел и уже вычисленных «частичных сумм». Таким образом, каждый шаг цикла поиска минимальной стоимости сложения будет состоять из нахождения двух минимальных чисел из множества, удаления этих чисел из множества $A$ и добавления в него результата их суммирования. В специальную переменную $minSum$ будем также каждый раз добавлять результат этого суммирования. Таким образом, количество элементов во множестве будет с каждым шагом уменьшаться на одно, и в конце, когда в нем останется единственный элемент, переменная $minSum$ будет содержать искомую стоимость сложения всех чисел.
Реализовать такой код достаточно просто, если реализовать множество $A$ в виде очереди с приоритетом.