转自 极光炫影 的blog
/*http://coder.buct.edu.cn:8080/JudgeOnline/showproblem?problem_id=1078*/
好久没有做题目了, 找了一个哈夫曼树的题目。
#include <iostream>
#include <functional>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n, e;
vector<int> s;
int i;
int total;
while(cin >> n)
{
s.clear();
for( i = 0; i < n; i++)
{
cin >> e;
s.push_back(e);
}
//建立堆
make_heap(s.begin(), s.end(), greater<int>());
total = 0;
int tmp = 0;
for(i = 0; i < n - 1; i++)
{
tmp = s[0];
pop_heap(s.begin(), s.end(),greater<int>());
s.pop_back();//移除最小元素
tmp += s[0];
pop_heap(s.begin(), s.end(), greater<int>());
s.pop_back();//移除次小元素
total += tmp;
s.push_back(tmp);
push_heap(s.begin(), s.end(), greater<int>());
}
cout << total << endl;
}
return 0;
}