資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告