给出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;
}
网友评论