本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
为了装修新房，你需要加工一些长度为正整数的棒材 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,4,3]
输出：14
解释：先将 2 和 3 连接成 5，花费 5；再将 5 和 4 连接成 9；总花费为 14
样例 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() < 2) {
return 0;
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : sticks) {
minHeap.add(num);
}
int res = 0;
while (minHeap.size() > 1) {
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 = 0,merge;
while(q1.size() + q2.size() > 1){
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
