学步园

//构造Huffman Tree,非叶子节点值总和即为结果，用最小优先队列维护<br /> #include<iostream><br /> #include<queue><br /> using namespace std;<br /> priority_queue<int,vector<int>,greater<int> > q;//最小优先队列，用greater<int>作为比较函数即可，less<int>则为最大优先队列<br /> int main()<br /> {<br /> //freopen("in.txt","r",stdin);<br /> long long int ans = 0;<br /> int n,node,first,second,new_node;<br /> scanf("%d",&n);<br /> for(int i = 0;i < n;++i)<br /> {<br /> scanf("%d",&node);<br /> q.push(node);<br /> }<br /> for(int i = 1;i <= n-1;++i)//对于构造n个叶子的Huffman Tree，只需n-1次结点构造，因为Huffman Tree是正则二元树，可以证明结点数目总比叶子数目少1<br /> {<br /> first = q.top();q.pop();<br /> second = q.top();q.pop();<br /> new_node = first + second;<br /> q.push(new_node);<br /> ans += new_node;<br /> }<br /> printf("%I64d/n",ans);//扑街结果原来是long long int的，还好有Discuss，不然真的不知道怎么老WA!</p> <p> return 0;<br /> }