Add All (Editorial)

Each time, two smallest numbers should be added together. This way, the total cost of adding all $n$ integers will be minimized. Since numbers can repeat, it is convenient to store them in a multiset.

Example

To minimize the cost of addition, add the numbers in the following order:

1. Add $1$ and $2$ to get $3$. Cost of addition is $3$.

2. Add $3$ and $3$ to get $6$. Cost of addition is $6$.

3. Add $4$ and $6$ to get $10$. Cost of addition is $10$.

The total cost of addition is 3 + 6 + 10 = 19.

Algorithm implementation

The input numbers are stored in a multiset $s$ (numbers can repeat). The two smallest numbers are always located at the beginning of the multiset.

multiset<long long> s;

Read the number of elements $n$.

scanf("%lld",&n);

Read the sequence of numbers and add them to the multiset $s$.

for (i = 0; i < n; i++)
{
  scanf("%lld",&x);
  s.insert(x);
}

The total cost of adding all numbers is computed in the variable $res$.

res = 0;

While there is more than one number in the multiset $s$, extract and add the two smallest elements, then add their sum back into $s$. The cost of adding numbers $a$ and $b$ is a + b, and this cost is added to $res$.

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;
}

When only one number remains in the multiset, print the answer — the value of the variable $res$.

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

Algorithm implementation — priority queue

Declare a priority queue $pq$, where the smallest element is always at the front.

priority_queue<long long, vector<long long>, greater<long long> > pq;

Read the number of elements $n$.

scanf("%lld",&n);

Read the sequence of numbers and add them to the priority queue $pq$.

scanf("%lld",&n);
for (i = 0; i < n; i++)
{
  scanf("%lld",&x);
  pq.push(x);
}

The total cost of adding all numbers is computed in the variable $res$.

res = 0;

While there is more than one number in the priority queue $pq$, extract and add the two smallest elements, then add their sum back into $pq$. The cost of adding numbers $a$ and $b$ is a + b, and this cost is added to $res$.

while (pq.size() > 1)
{
  a = pq.top(); pq.pop();
  b = pq.top(); pq.pop();
  pq.push(a + b);
  res += a + b;
}

When only one number remains in the priority queue, print the answer – the value of the variable $res$.

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

Java implementation

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    PriorityQueue<Long> pq = new PriorityQueue<Long>();
    for(int i = 0; i < n; i++)
    {
      long val = con.nextLong();
      pq.add(new Long(val));
    }
    long Result = 0;
    while(pq.size() > 1)
    {
      long a = pq.poll();
      long b = pq.poll();
      pq.add(a + b);
      Result += a + b;
    }
    System.out.println(Result);    
  }
}

Python implementation

Declare a priority queue $q$, where the smallest element is always at the front.

from queue import PriorityQueue
q = PriorityQueue()

Read the input data.

n = int(input())
lst = map(int,input().split())

Add the numbers to the queue $q$.

for x in lst:
  q.put(x)

The total cost of adding all numbers is computed in the variable $res$.

res = 0

While there is more than one number in the priority queue $q$, extract and add the two smallest elements, then add their sum back into $q$. The cost of adding numbers $a$ and $b$ is a + b, and this cost is added to $res$.

while q.qsize() > 1:
  a = q.get()
  b = q.get()
  q.put(a + b)
  res += a + b

When only one number remains in the priority queue, print the answer — the value of the variable $res$.

print(res)