POJ3253

poj3253:http://poj.org/problem?id=3253,简单的哈夫曼问题

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

struct cmp
{
	bool operator() (unsigned int x,unsigned int y)
	{
		return x>y;
	}
};

priority_queue<unsigned int,vector<unsigned int>,cmp> q;
unsigned int ans=0;
unsigned int total=0;

void doit()
{
	unsigned int sum=0;
	
	while(!q.empty())
	{
		sum+=q.top();
		q.pop();
		if(!q.empty())
		{
			sum+=q.top();
			q.pop();
			if(sum!=total)
				q.push(sum);
		}
		ans+=sum;
		sum=0;	
	}
}

int main()
{
	unsigned int n;
//	ifstream cin("1.txt");
	cin>>n;
	if(1==n)
	{
		ans=0;
	}
	else
	{	
		for(unsigned int i=0;i<n;i++)
		{
			unsigned int temp;
			cin>>temp;
			q.push(temp);
			total+=temp;
		}
		doit();
	}
	cout<<ans<<endl;
	
	return 0;
}

注意此题的数值范围，最后结果用unsigned int或long保存，不然会数据会溢出，另外，注意n=1时，花费为0。
这里优先队列的用法，可以设置比较函数，重载（）运算符，还有一种用来比较结构体的方法，重载>操作符。

struct node
{
    int x, y;
    friend bool operator < (node a, node b)
    {
        return a.x > b.x; //结构体中，x小的优先级高
    }
};
priority_queue<node>q;//定义方法