给出 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;
- }
来源: http://www.jianshu.com/p/a33e8872f94a