สมมติว่าเรามีแท่งไม้ที่มีความยาวจำนวนเต็มบวก เราสามารถเชื่อมไม้ที่มีความยาว X และ Y สองแท่งเข้าด้วยกันเป็นแท่งเดียวโดยจ่ายราคา X + Y การดำเนินการนี้จะดำเนินการจนกว่าจะเหลือแท่งเดียว เราต้องหาต้นทุนขั้นต่ำในการเชื่อมต่อแท่งที่ให้มาทั้งหมดเป็นแท่งเดียวด้วยวิธีนี้ ดังนั้นหากสแต็กเป็น [2,4,3] ผลลัพธ์จะเป็น 14
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนด pq คิวลำดับความสำคัญสูงสุดของฮีป
- แทรกองค์ประกอบทั้งหมดของ s ลงใน pq
- ตอบ :=0
- ในขณะที่ pq มีมากกว่าหนึ่งองค์ประกอบ
- temp :=ด้านบนของคิว ลบ top จาก pq
- temp :=temp + องค์ประกอบด้านบนของ pq และลบออกจาก pq
- ans :=ans + อุณหภูมิ
- ใส่อุณหภูมิลงใน pq
- คืนสินค้า
ตัวอย่าง(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
