MNMX- keeps on showing WA!! Run it on ur system and tell me in what condition the answer is wrong???

general
1

#include
#include

using namespace std;

int main()
{
     int t,i=0;
     cin>>t;

     vector <long int> ans(t);

     while(i<t)
     {
          long int n,j=0;
          cin>>n;
          long int z;
          vector <int> a(n);
          for(;j<n;j++)
               cin>>a[j];
           long int cost=0,k;
           for(j=0;j<n-1;j++)
           {
                if(a[0]<a[1])
                {
                     cost+=a[0];
                     k=1;
                }
                else
                {
                     cost+=a[1];
                     k=0;
                }
                if(k==0)
                {
                     for(z=0;z<n-j-1;z++)
                     {
                          a[z]=a[z+1];
                     }
                }
                else
                {
                     for(z=1;z<n-j-1;z++)
                     {
                          a[z]=a[z+1];
                     }
                }
           }
           ans[i]=cost;

         i++;
     }
     for(i=0;i<t;i++)
          cout<<ans[i]<<"\n";
}
2

Make some observations dear. You will see that he can always form pairs of an element with minimum element, and hence remove with minimum cost.

Eg, sample I/o 2-

{4,2,5}.

Make pair of {4,2}, remove 4 at cost of 2. Then make pair {2,5}, remove 5 at cost of 2. Keep doing this until only 2 is left.

The cost incurred is MinimumElement*(N-1) . Take care of data types, int cannot hold for large values!

BTW

if(a[0]<a[1])
                {
                     cost+=a[0];
                     k=1;
                }

This is wrong as it doesnt guarantee that answer will be minimum. Take case of {90,100,2,5}. Answer is 6. What will your algorithm yield?

3

@root00198

A failing test case for your solution is following array/

5 2 1

Your code gives answer 3 while correct answer is two…

Your solution fails on cases where

first two elements of given array don’t contain minimum element…

Remember, this operation can be performed at any pair of consecutive elements of array…

So array 5 7 6 8 2 6 4 changes as follows

5 7 6 8 2 4

5 7 6 8 2

5 7 6 2

5 7 2

5 2

2

All N-1 operations at cost 2, the minimum element…

Answer is (N-1)*minimum_element

4

Thanks a lot