Hər şeyi əlavə et#1228

Hər şeyi əlavə et (Həll təhlili)

Hər dəfə iki ən kiçik ədədi toplamaq lazımdır. Bu yolla bütün $n$ ədədlərinin toplanmasının ümumi dəyəri minimal olacaq. Ədədlər təkrarlana biləcəyi üçün onları çoxüzvlükdə saxlamaq əlverişlidir.

Nümunə

Toplama xərclərini minimallaşdırmaq üçün ədədləri aşağıdakı qaydada əlavə edəcəyik:

$1$ və $2$ toplayırıq, $3$ alırıq. Toplama xərci $3$ .
$3$ və $3$ toplayırıq, $6$ alırıq. Toplama xərci $6$ .
$4$ və $6$ toplayırıq, $10$ alırıq. Toplama xərci $10$ .

Bütün toplamanın ümumi xərci $3 + 6 + 10 = 19$ 3 + 6 + 10 = 19.

Alqoritmin həyata keçirilməsi

Giriş ədədlərini çoxüzvlükdə $s$ saxlayırıq (ədədlər təkrarlana bilər). İki ən kiçik ədəd çoxüzvlüyün başlanğıcında olur.

multiset<long long> s;

Ədədlərin sayını oxuyuruq $n$ .

scanf("%lld",&n);

Toplamaların ardıcıllıqla oxunması və onları çoxüzvlüyə $s$ əlavə edirik.

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

Bütün ədədlərin toplama xərclərini $r es$ dəyişənində hesablayırıq.

res = 0;

Çoxüzvlükdə $s$ bir ədəddən çox ədəd olduğu müddətcə onun iki ən kiçik elementini çıxarır və toplayırıq, sonra onların cəmini yenidən $s$ -ə əlavə edirik. $a$ və $b$ ədədlərinin toplama xərci $a + b$ a + b-yə bərabərdir və o, $r es$ -ə əlavə edilir.

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

C++

Çoxüzvlükdə yalnız bir ədəd qaldıqda, cavabı - $r es$ dəyişəninin dəyərini çıxarırıq.

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

Prioritet növbəsi ilə həyata keçirilməsi

Ən önündə həmişə ən kiçik elementin olduğu prioritet növbəsi $pq$ elan edirik.

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

Ədədlərin sayını oxuyuruq $n$ .

scanf("%lld",&n);

Toplamaların ardıcıllığını oxuyur və onları prioritet növbəsinə $pq$ əlavə edirik.

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

Bütün ədədlərin toplama xərclərini $r es$ dəyişənində hesablayırıq.

res = 0;

Prioritet növbəsi $pq$ bir ədəddən çox ədəd olduğu müddətcə onun iki ən kiçik elementini çıxarır və toplayırıq, sonra onların cəmini yenidən $pq$ -yə əlavə edirik. $a$ və $b$ ədədlərinin toplama xərci $a + b$ a + b-yə bərabərdir və o, $r es$ -ə əlavə edilir.

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

C++

Prioritet növbəsində yalnız bir ədəd qaldıqda, cavabı - $r es$ dəyişəninin dəyərini çıxarırıq.

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

Java ilə həyata keçirilməsi

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

Java

Python ilə həyata keçirilməsi

Ən önündə həmişə ən kiçik elementin olduğu prioritet növbəsi $q$ elan edirik.

from queue import PriorityQueue
q = PriorityQueue()

Giriş məlumatlarını oxuyuruq.

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

Toplamaları növbəyə $q$ əlavə edirik.

for x in lst:
  q.put(x)

Bütün ədədlərin toplama xərclərini $r es$ dəyişənində hesablayırıq.

res = 0

Növbədə $q$ bir ədəddən çox ədəd olduğu müddətcə onun iki ən kiçik elementini çıxarır və toplayırıq, sonra onların cəmini yenidən $q$ -yə əlavə edirik. $a$ və $b$ ədədlərinin toplama xərci $a + b$ a + b-yə bərabərdir və o, $r es$ -ə əlavə edilir.

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

Növbədə yalnız bir ədəd qaldıqda, cavabı - $r es$ dəyişəninin dəyərini çıxarırıq.

print(res)