Advertisement
imashutosh51

Minimum cost of ropes to join

Jul 23rd, 2022
24
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. //for eg. 2 3 4 6
  2. //let's find answer 2+3 ans=5,new array=[5,4,6] new_sum=5+4 or 5 is actually(2+3) so ans=2+3+2+3+4,new array=[9,6] new_sum=15
  3. //9 is actually 2+3+4 so new sum=(((2+3)+2+3+4)+2+3+4+6) so the element we chose in first time is repeating so why not choose
  4. //small element early for less repeating of elements so used min_heap
  5. class Solution
  6. {
  7.     public:
  8.     //Function to return the minimum cost of connecting the ropes.
  9.     long long minCost(long long arr[], long long n) {
  10.         priority_queue<long long int,vector <long long int>,greater<long long int>> pq;
  11.         for(long long int i=0;i<n;i++) pq.push(arr[i]);
  12.         long long int res=0;
  13.         while(pq.size()>1){
  14.             long long int t1=pq.top();pq.pop();
  15.             long long int t2=pq.top();pq.pop();
  16.             res+=(t1+t2);
  17.             pq.push(t1+t2);
  18.         }
  19.         return res;
  20.     }
  21. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement