Chi phí tối thiểu để kết nối các thanh trong C ++

Giả sử chúng ta có một số que có độ dài là số nguyên dương. Chúng ta có thể nối hai que có độ dài X và Y bất kỳ thành một que bằng cách trả chi phí X + Y. Việc này sẽ được thực hiện cho đến khi còn lại một que. Chúng ta phải tìm chi phí tối thiểu để kết nối tất cả các que đã cho thành một que theo cách này. Vì vậy, nếu ngăn xếp là [2,4,3], thì đầu ra sẽ là 14.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định pq hàng đợi ưu tiên heap tối đa
• chèn tất cả các phần tử của s vào pq
• ans:=0
• trong khi pq có nhiều hơn một phần tử
  • temp:=đầu hàng đợi, xóa đầu khỏi pq
  • temp:=temp + phần tử trên cùng của pq và xóa khỏi pq
  • ans:=ans + temp
  • chèn tạm thời vào pq
• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

[2,4,3]

Đầu ra

14