i have a doubt that why can’t we use greedy method of selecting the minimum and take its minimum adjacent value and add it to penalty.we can do it till last element is left.
my code is down below:
#include <bits/stdc++.h>
using namespace std;
int minm(int ar[],int n)
{
int x;
long int t=10000000000;
for(int i=0;i<=n;i++)
{
if(t>ar[i])
{
x=i;
t=ar[i];
}
}
return x;
}
int main() {
int n,q;
int ar[400];
cin>>q;
while(q>0){
cin>>n;
int mi,i;
for (int i=0;i<n;i++)
{
cin>>ar[i];
}
long int s=0;
for(int j=n-1;j>0;j–){
mi=minm(ar,j);
//printf("%d ",mi); //if first element is the minimum
if(ar[0]==ar[mi]){
if(ar[1]>=ar[j])
{
ar[0]+=ar[j];
s=s+ar[0];
}
else
{
ar[0]+=ar[1];
s=s+ar[0];
for(i=1;i<j;i++)
{ar[i]=ar[i+1];}
}
}
else if(ar[j]==ar[mi]){ //if any middle element is the minimum
if(ar[0]>=ar[j-1])
{
ar[j-1]+=ar[j];
s=s+ar[j-1];
}
else
{
ar[0]+=ar[j];
s+=ar[0];
}
}
else{
if(ar[mi-1]>=ar[mi+1]) ////if last element is the minimum
{
ar[mi]+=ar[mi+1];
s+=ar[mi];
for(i=mi+1;i<j;i++)
{ar[i]=ar[i+1];}
}
else
{
ar[mi-1]+=ar[mi];
s+=ar[mi-1];
for(i=mi;i<j;i++)
{ar[i]=ar[i+1];}
}
}
}
printf("%ld\n",s);
q–;
}
return 0;
}