I wrote code for the problem : Connect n ropes with minimum cost
The link for the problem is : Connect n ropes with minimum cost - GeeksforGeeks
It is based on Heap data structure and greedy algo. I traverse the input array and put the values in MinHeap. If the size of the heap is greater than 2 , I pop the first two elements and add their sum to the answer variable and then push the sum of the popped 2 elements back in MinHeap. In the end when I traverse the whole array and exit, I pop the remaining 2 elements in the MinHeap and add their sum to the answer variable.
My code:
Link : iZtZt6 - Online C++ Compiler & Debugging Tool - Ideone.com
#include<bits/stdc++.h>
using namespace std;
int main(){
priority_queue<int> q;
int t;
cin>>t;
while(t--){
long long int n;
cin>>n;
long long int arr[n];
for(long long int i=0;i<n;i++) cin>>arr[i];
priority_queue< long long int, vector<long long int> ,greater<long long int> > q;
long long int ans=0;
for(long long int i=0;i<n;i++){
q.push(arr[i]);
if(q.size()>2){
long long int x = q.top(); q.pop();
long long int y = q.top(); q.pop();
ans+=(x+y);
q.push(x+y);
}
}
long long int a= q.top(); q.pop();
long long int b= q.top(); q.pop();
ans+=(a+b);
cout<<ans<<"\n";
}
}
In the original solution the whole array elements are traversed and put in the MinHeap .After doing that they use a while loop which runs while the size of the MinHeap is greater than equal to 2 and the top 2 elements are popped in each iteration and their sum is added to the answer variable. Why does that approach works and not mine.
Please Help.