连接C ++中的Sticks的最低成本

假设我们有一些长度为正整数的摇杆。我们可以通过支付X + Y的费用将任意两个长度为X和Y的杆连接到一根杆中。此操作将执行到剩余一根杆为止。我们必须找到以这种方式将所有给定杆连接到一根杆的最低成本。因此，如果堆栈为[2,4,3]，则输出为14。

为了解决这个问题，我们将遵循以下步骤-

• 定义最大堆优先级队列pq

• 将s的所有元素插入pq

• 回答：= 0

• 而pq具有多个元素

• temp：=队列顶部，从pq删除顶部

• temp：= temp + pq的顶部元素，并从pq中删除

• ans：= ans + 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