# 1167. Minimum Cost to Connect Sticks 连接棒材的最低费用

@TOC

## # 题目描述

You have some sticks with positive integer lengths.

You can connect any two sticks of lengths `X` and `Y` into one stick by paying a cost of `X + Y`. You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Example 1:

``````Input: sticks = [2,4,3]
Output: 14
``````

Example 2:

``````Input: sticks = [1,8,3,5]
Output: 30
``````

Constraints:

1. `1 <= sticks.length <= 10^4`
2. `1 <= sticks[i] <= 10^4`

## # 解题方法

### # 小根堆

C++代码如下：

``````class Solution {
public:
int connectSticks(vector<int>& sticks) {
priority_queue<int, vector<int>, greater<int>> que;
for (int stick : sticks) {
que.push(stick);
}
int res = 0;
while (!que.empty()) {
int first = que.top(); que.pop();
if (!que.empty()) {
int second = que.top(); que.pop();
int sum = first + second;
res += sum;
que.push(sum);
}
}
return res;
}
};
``````

## # 日期

2019 年 9 月 23 日 —— 昨夜睡的早，错过了北京的烟火