为了装修新房，你需要加工一些长度为正整数的棒材 sticks。
如果要将长度分别为 X 和 Y 的两根棒材连接在一起，你需要支付 X + Y 的费用。 由于施工需要，你必须将所有棒材连接成一根。
返回你把所有棒材 sticks 连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。
- 1≤sticks.length≤10^4
- 1≤sticks[i]≤10^4
在线评测地址：https://www.lintcode.com/problem/minimum-cost-to-connect-sticks/?utm_source=sc-bky-zq
样例 1:
输入：
[,,]
输出：
解释：先将 和 连接成 ，花费 ；再将 和 连接成 ；总花费为
样例 2:
输入：
[,,,]
输出：
【题解】
根据题意，考虑贪心，我们每次将所有棒材的最短的两根合并，将合并后的棒材放入棒材堆，重复合并最短的，直到棒材只剩下一根。
// minheap 暴力
// 直接将所有值压入minheap，每次取前两个值相加成merge，同时将merge压入minheap
public class Solution {
/**
* @param sticks: the length of sticks
* @return: Minimum Cost to Connect Sticks
*/
public int MinimumCost(List<Integer> sticks) {
if (sticks.size() < ) {
return ;
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : sticks) {
minHeap.add(num);
}
int res = ;
while (minHeap.size() > ) {
int merge = minHeap.poll() + minHeap.poll();
res += merge;
minHeap.add(merge);
}
return res;
}
}
// 排序，双队列
// 先将数组排序，然后开始合并，合并后的值放入q2末尾，能够保证q2中被押入的值是
// 一定大于前面的值的，每次合并我们考虑q1,q2非空以及比较q1[0]和q2[0]的大小
public class Solution {
/**
* @param sticks: the length of sticks
* @return: Minimum Cost to Connect Sticks
*/
public int MinimumCost(List<Integer> sticks) {
Collections.sort(sticks);
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
for (int i : sticks) {
q1.add(i);
}
int res = ,merge;
while(q1.size() + q2.size() > ){
if(q2.isEmpty()){
merge = q1.poll();
merge += q1.poll();
q2.add(merge);
res += merge;
}
else if (q1.isEmpty()){
merge = q2.poll();
merge += q2.poll();
q2.add(merge);
res += merge;
}
else {
if(q1.peek() > q2.peek()){
merge = q2.poll();
}
else {
merge = q1.poll();
} if (q1.isEmpty()){
merge += q2.poll();
q2.add(merge);
res += merge;
}
else if(q2.isEmpty()){
merge += q1.poll();
q2.add(merge);
res += merge;
}
else {
if(q1.peek() > q2.peek()){
merge += q2.poll();
q2.add(merge);
res += merge;
}
else {
merge += q1.poll();
q2.add(merge);
res += merge;
}
}
}
}
return res;
}
}
更多题解参见：https://www.jiuzhang.com/solution/minimum-cost-to-connect-sticks/?utm_source=sc-bky-zq