the question with code MNMX is not accepting my solution, whereas I saw the solutions of the accepted code and they are not yielding correct answers. What am I supposed to do?
my code: #include
using namespace std;
int main() {
// your code goes here
int t; cin>>t;
while(t–)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int i=0;
int j=1;
int cost=0;
while(i<n && j<n)
{
if(i<j)
{
if(a[i]>a[j])
{
cost+=a[j];
i=j+1;
}
else
{
cost+=a[i];
j++;
}
}
else
{
if(a[i]>a[j])
{
cost+=a[j];
i++;
}
else
{
cost+=a[i];
j=i+1;
}
}
}
cout<<cost<<endl;
}
return 0;
}
First thing…Please please comment your code …otherwise how others are going to understand your approach???It will draw less response from the community.
Secondly,since I am not understanding your solution…I want to tell you mine.
Understand that in the array there will be a number that is minimum among all the numbers since all the numbers in the array are given distinct.
So the minimum cost for an operation would occur when you remove elements that are adjacent to the minimum element.
Say the numbers are 20,15,3,11,12,10. To have minimum cost , we would first like to remove the element adjacent to the minimum element.In this case, 3 is the min. So remove either 15 or 11.
Now the array looks like 20,3,11,12,10-> we removed 15.The cost incurred is 3.
Next try to remove either 20 or 11.What will be the cost??3 again.That will be the minimum also as 3 is the min. element.
So if you continue this way…to remove n-1 elements where n is the size of the array, the total cost would be (n-1)*min(all the elements present in the array initially). Since you are not removing the minimum element, the arrays that are obtained after removing the elements adjacent to minimum will still contain the minimum element.
I hope it is clear…feel free to ask in case of doubt