Додати всі (Розбір)

Кожного разу слід складати два найменших числа. Таким чином, сумарна вартість складання всіх $n$ чисел буде мінімальною. Оскільки числа можуть повторюватися, їх зручно зберігати в мультимножині.

Приклад

Для мінімізації вартості складання будемо складати числа в такому порядку:

1. Складаємо $1$ і $2$, отримаємо $3$. Вартість складання $3$.

2. Складаємо $3$ і $3$, отримаємо $6$. Вартість складання $6$.

3. Складаємо $4$ і $6$, отримаємо $10$. Вартість складання $10$.

Загальна вартість складання дорівнює 3 + 6 + 10 = 19.

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

Вхідні числа зберігаємо в мультимножині $s$ (числа можуть повторюватися). Два найменших числа завжди розташовані на початку мультимножини.

multiset<long long> s;

Читаємо кількість чисел $n$.

scanf("%lld",&n);

Читаємо послідовність доданків і додаємо їх в мультимножину $s$.

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

У змінній $res$ обчислюємо вартість складання всіх чисел.

res = 0;

Поки в мультимножині $s$ більше одного числа, дістаємо і складаємо два його найменших елементи і додаємо їхню суму назад в $s$. Вартість складання чисел $a$ і $b$ дорівнює a + b, і вона додається до $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;
}

Коли в мультимножині залишається тільки одне число, виводимо відповідь — значення змінної $res$.

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

Реалізація за допомогою черги з пріоритетами

Оголосимо чергу з пріоритетами $pq$, на початку якої завжди знаходиться найменший елемент.

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

Читаємо кількість чисел $n$.

scanf("%lld",&n);

Читаємо послідовність доданків і додаємо їх в чергу з пріоритетами $pq$.

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

У змінній $res$ обчислюємо вартість складання всіх чисел.

res = 0;

Поки в черзі $pq$ більше одного числа, дістаємо і складаємо два його найменших елементи і додаємо їхню суму назад в $pq$. Вартість складання чисел $a$ і $b$ дорівнює a + b, і вона додається до $res$.

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

Коли в черзі залишається тільки одне число, виводимо відповідь — значення змінної $res$.

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

Java реалізація

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 реалізація

Оголосимо чергу з пріоритетами $q$, на початку якої завжди знаходиться найменший елемент.

from queue import PriorityQueue
q = PriorityQueue()

Читаємо вхідні дані.

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

Додамо доданки в чергу $q$.

for x in lst:
  q.put(x)

У змінній $res$ обчислюємо вартість складання всіх чисел.

res = 0

Поки в черзі $q$ більше одного числа, дістаємо і складаємо два його найменших елементи і додаємо їхню суму назад в $q$. Вартість складання чисел $a$ і $b$ дорівнює a + b, і вона додається до $res$.

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

Коли в черзі залишається тільки одне число, виводимо відповідь — значення змінної $res$.

print(res)