There are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.
For example if we are given 4 ropes of lengths 4, 3, 2 and 6. We can connect the ropes in following ways.
1) First connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6 and 5.
2) Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.
3) Finally connect the two ropes and all ropes have connected.
Diff ways to connect
1) As it is... count = 4+3 = 7 , count = 7(previous)+ 7+2 = 16 , count = 16(previous)+9+6 =31.
2) Longest first
Array = 6,4,3,2
count = 6+4 =10 , count = 10+10+3=23 , count = 23+23+2 =48.
From above discussion we can understand that lengths of the ropes which are picked first are included more than once in total cost, hence we can say that choosing smallest ropes first will give optimal solution.
code
#include <iostream>
#include <stdio.h>
#include <array>
#include <algorithm>
using namespace std;
#define MAX 100
#define gc getchar_unlocked
inline int scan(){register int n=0,c=gc();while(c<'0'||c>'9')c=gc();while(c<='9'&&c>='0')n=(n<<1)+(n<<3)+c-'0',c=gc();return n;}
int getCount(int n[],int len,int c)
{
int i=0;
if(n[i+1]!=9999){
n[i+1]+=n[i];
n[i]=9999;
c+=n[i+1];
sort(n,n+len);
}
if(n[i+1]==9999)return c;
if(len>0) getCount(n,len-1,c);
}
int main()
{
int len=scan();
int j = len;
int n[MAX];
int sum=0;
int i = 0;
while(j--){
n[i++]=scan();
}
j=len;
sort(n,n+len);
sum=getCount(n,len,sum);
cout<<"Sum is="<<sum;
return 0;
}
//STDIN : 4 2 4 3 6
Complexity : O(n^2 logn)
O(n) to get all ropes * O(nlogn) sorting array each time.
See running code : http://ideone.com/89GG37
Solution 2 : Use Min Heap instead sorting array every time
Logic:
1) Store array's element in Min heap.
do
2) Get first minimum and second minimum
3) Add them and store result in min heap and update "SUM".
while(heap's length > 1)
=> Try to implement yourself :)
For example if we are given 4 ropes of lengths 4, 3, 2 and 6. We can connect the ropes in following ways.
1) First connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6 and 5.
2) Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.
3) Finally connect the two ropes and all ropes have connected.
Diff ways to connect
1) As it is... count = 4+3 = 7 , count = 7(previous)+ 7+2 = 16 , count = 16(previous)+9+6 =31.
2) Longest first
Array = 6,4,3,2
count = 6+4 =10 , count = 10+10+3=23 , count = 23+23+2 =48.
From above discussion we can understand that lengths of the ropes which are picked first are included more than once in total cost, hence we can say that choosing smallest ropes first will give optimal solution.
code
#include <iostream>
#include <stdio.h>
#include <array>
#include <algorithm>
using namespace std;
#define MAX 100
#define gc getchar_unlocked
inline int scan(){register int n=0,c=gc();while(c<'0'||c>'9')c=gc();while(c<='9'&&c>='0')n=(n<<1)+(n<<3)+c-'0',c=gc();return n;}
int getCount(int n[],int len,int c)
{
int i=0;
if(n[i+1]!=9999){
n[i+1]+=n[i];
n[i]=9999;
c+=n[i+1];
sort(n,n+len);
}
if(n[i+1]==9999)return c;
if(len>0) getCount(n,len-1,c);
}
int main()
{
int len=scan();
int j = len;
int n[MAX];
int sum=0;
int i = 0;
while(j--){
n[i++]=scan();
}
j=len;
sort(n,n+len);
sum=getCount(n,len,sum);
cout<<"Sum is="<<sum;
return 0;
}
//STDIN : 4 2 4 3 6
Complexity : O(n^2 logn)
O(n) to get all ropes * O(nlogn) sorting array each time.
See running code : http://ideone.com/89GG37
Solution 2 : Use Min Heap instead sorting array every time
Logic:
1) Store array's element in Min heap.
do
2) Get first minimum and second minimum
3) Add them and store result in min heap and update "SUM".
while(heap's length > 1)
=> Try to implement yourself :)
