UVA 10954 Add All 全部相加 （Huffman编码）

题意：给你n个数的集合，每次选两个删除，把它们的和放回集合，直到集合的数只剩下一个，每次操作的开销是那两个数的和，求最小开销。

Huffman编码。Huffman编码对于着一颗二叉树，这里的数对应着单词出现的频度，每次合并深度最大的结点，选频度最小的两个。

用两个队列类似归并排序，合并一下。

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

int q1[maxn];

int q2[maxn];

#define GetMin(x)\

if(head1>=rear1 || (head2<rear2 && q1[head1]>q2[head2])) x = q2[head2++];\

else x = q1[head1++];

int main()

{

    int n,x;

    while(scanf("%d",&n),n){

        int head1 = ,rear1 = n,head2 = ,rear2 = ;

        for(int i = ; i < n; i++) scanf("%d",q1+i);

        int ans = ;

        sort(q1,q1+n);

        int a = q1[head1++];

        int b = q1[head1++];

        ans += q2[rear2++] = a+b;

        for(int i = ; i < n; i++){

            GetMin(a) GetMin(b)

            ans += q2[rear2++] = a+b;

        }

        printf("%d\n",ans);

    }

    return ;

}

效率要求不高的时候可以用优先队列

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int n,x;

    while(~scanf("%d",&n)&&n){

        priority_queue<int,vector<int>,greater<int> >q;

        for(int i = ; i < n ;i++) { scanf("%d",&x); q.push(x); }

        int ans = ;

        for(int i = ; i < n; i++){

            int a = q.top(); q.pop();

            int b = q.top(); q.pop();

            ans += a+b;

            q.push(a+b);

        }

        printf("%d\n",ans);

    }

    return ;

}