791. 合并数字贪心算法
791. 合并数字贪心算法
给出n个数，现在要将这n个数合并成一个数，每次只能选择两个数a,b合并，每次合并需要消耗a+b的能量，输出将这n个数合并成一个数后消耗的最小能量。
注意事项
2 <= n <= 50000，合并后的数字不会超过int范围
样例
给出[1,2,3,4]，返回 19。
解释：
选择1,2合并，消耗3能量，现在为[3,4,3]，选择3,3合并，消耗6，现在为[6,4]，剩下两个数合并，消耗10，一共消耗19。给出[2,8,4,1],返回 25。
解释：
选择1,2合并，消耗3能量，现在为[8,4,3]，选择3,4合并，消耗7，现在为[7,8]，剩下两个数合并，消耗15，一共消耗25。贪心算法
一个显而易见的策略是每次我们都找到最小的两个来合并，这样最后加起来的能量应该是最小的。这样想倒是很简单，我们可以对vector<int>进行排序,取出前两个（从vector中删掉）进行相加，然后把结果重新放入vector<int>中。然后再排序，重新进行上述步骤，直到vector中只剩下一个数据，就是我们要找的。但是这样显然是非常耗时的，且不说vector排序耗时，删除也是很耗时的。 一种比较好的数据结构是优先队列，这个是用堆实现的，queue这个数据结构。
priority_queue 优先队列
priority_queue<Type, Container, Functional>Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。后两种可以不写，如果不写，container默认为vector，functional默认为大的在队首。 成员函数主要有：
函数 | 功能 |
|---|---|
empty(); | //判断是否为空 |
size(); | //返回大小 |
pop(); | //删除队首 |
push(); | //入队 |
top(); | //返回队首 |
默认大元素优先，因为我们要用小元素优先，所以应该构造,：
priority_queue<int,vector<int>,greater<>> q
functional参数是一个bool型的比较参数，和STL中sort里的那个参数是一样的。可以自定义。
了解了这个，剩下的程序就比较简单了：
int mergeNumber(vector<int> &numbers) {
int res=0;
if(numbers.size()==1)
return *numbers.begin();
priority_queue<int,vector<int>,greater<>> q; //优先队列，小的在前
for(auto n:numbers) //所有数据入队
{
q.push(n);
}
int sz=numbers.size();
int q1=0;
int q2=0;
while(sz!=1)
{
q1=q.top(); //取第一个元素
q.pop();
q2=q.top(); //取第二个元素
q.pop();
res+=q1+q2; //和累加起来
q.push(q1+q2); //和入队
sz--; //sz--
}
return res;
}