Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //for eg. 2 3 4 6
- //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
- //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
- //small element early for less repeating of elements so used min_heap
- class Solution
- {
- public:
- //Function to return the minimum cost of connecting the ropes.
- long long minCost(long long arr[], long long n) {
- priority_queue<long long int,vector <long long int>,greater<long long int>> pq;
- for(long long int i=0;i<n;i++) pq.push(arr[i]);
- long long int res=0;
- while(pq.size()>1){
- long long int t1=pq.top();pq.pop();
- long long int t2=pq.top();pq.pop();
- res+=(t1+t2);
- pq.push(t1+t2);
- }
- return res;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement