ツリー-スタック構造練習-果物を統合したハフマンツリー(C/C++実装)

木-山の構造の練習-果物のハフマンの木を合併します
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
一つの果樹園では、多くの果物がすべて打たれ、果物の種類によって異なる山に分かれている.すべての果物をたくさん合成することにした.
合併するたびに、多くの場合、2つの果物を統合することができ、消費された体力は2つの果物の重量の和に等しい.すべての果物はn-1回の合併を経て、1山しか残っていないことがわかる.多くの場合、果物を合併する際に消費される体力は、合併するたびに消費される体力の和に等しい.
これらの果物を家に運ぶのに力を入れなければならないので、果物を合併するときはできるだけ体力を節約しなければならないことが多い.各果物の重量が1であり、既知の果物の種類数と各果物の数を仮定すると、あなたの任務は合併の順序案を設計し、多くの体力を最小限に抑え、この最小の体力消費値を出力することです.
例えば3種類の果物があり、数は1,2,9の順である.まず1、2スタックを統合することができ、新しいスタックの数は3で、体力を消費するのは3です.次に、新しいスタックを元の第3のスタックと統合し、新しいスタックを得、数は12であり、体力は12である.そのため、体力=3+12=15を多く消費します.15が最小の体力消費値であることが証明される.
 
Input
1行目は整数n(1<=n<=10000)であり、果物の種類数を表す.2行目はn個の整数を含み、スペースで区切られ、i番目のai(1<=ai<=20000)はi番目の果物の数である.
 
Output
出力には1つの整数、すなわち最小の体力消費値しか含まれない行が含まれます.入力データは、この値が2^31未満であることを保証します.
 
Sample Input

3
1 2 9

Sample Output

15

Hint
毎回最小の2つを合わせて元のスタックに入れて並べ替えます
C実装コード(配列シミュレーションスタック)

#include 
#include 
void qs(int a[], int l, int r);
int main()
{
    int n, a[20010], i;
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    qs(a, 1, n);  //       ，       
    long count = 0;
    int x = 0, y = 0, j, k, s;
    i = 1;
    while(i != n)
    {
        x = a[i]; i++;
        y = a[i]; i++;
        s = x + y;
        count += s;
        for(k = i; k <= n; k++)
        {
            if(a[k] >= s) break;
        }
        for(j = n + 1; j > k; j--)
        {
            a[j] = a[j - 1];
        }
        a[k] = s;
        n++;
    }
    printf("%ld
", count);
    return 0;
}
void qs(int a[], int l, int r)  //     
{
    int i = l, j = r, key = a[l];
    if(l >= r) return ;
    while(i < j)
    {
        while(i < j && a[j] >= key)
        {
            j--;
        }
        a[i] = a[j];
        while(i < j && a[i] <= key)
        {
            i++;
        }
        a[j] = a[i];
    }
    a[i] = key;
    qs(a, l, i - 1);
    qs(a, i + 1, r);
}

C++実装(優先キュー適用)

// #include  //   ，  oj   
#include 
#include 
#include 
using namespace std;

int main()
{
    // priority_queue  p; //           ；
    priority_queue , greater > p; //        
    int n, i, x;
    long long a = 0, sum = 0;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        scanf("%d", &x);
        p.push(x);
    }
    while(p.size() > 1)
    {
        a = p.top();
        p.pop();
        a += p.top();
        p.pop();
        sum += a;
        p.push(a);
    }
    p.pop(); //        
    printf("%lld
", sum);
    return 0;
}