数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法学C++ 中的连接木棍的最小成本
假设我们有一些整数长度的木棍。我们能以 X + Y 的代价将长度为 X 和 Y 的两根木棍连接成一根木棍。这样一直进行，直到只剩下一根木棍。我们需要找出以这种方式将所有给定木棍连接成一根木棍的最小成本。所以堆栈是[2, 4, 3]，那么输出就是 14。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个 max 堆优先队列 pq
- 将 s 的所有元素插入到 pq 中
- ans := 0
- 只要 pq 中的元素多于一个
- temp := 队列的顶部元素，从 pq 中删除顶部元素
- temp := temp + pq 中的顶部元素，并将其从 pq 中删除
- ans := ans + temp
- 将 temp 插入到 pq 中
- 返回 ans
示例（C++）
让我们看一看以下实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int connectSticks(vector<int>& s) {
priority_queue <int, vector<int>, greater<int> > pq;
for(int i =0;i<s.size();i++)pq.push(s[i]);
int ans = 0;
while(pq.size()>1){
int temp = pq.top();
pq.pop();
temp += pq.top();
pq.pop();
ans+=temp;
pq.push(temp);
}
return ans;
}
};
main(){
vector<int> v = {2,4,3};
Solution ob;
cout <<ob.connectSticks(v);
}输入
[2,4,3]
输出
14
更新于： 2020 年 4 月 30 日
348 次浏览
广告