10041-Vito’s family-Solution hints

https://uva.onlinejudge.org/external/100/10041.pdf


This is a easy problem . Solving techniques is given below :

1 . In this problem it is said to determine the shortest distance of a given set of numbers as defined Vito's relatives house no . Vito wants to minimize the total distance .

2 . Minimizing the total distance or determining sum of minimal distance we need to sort the given set of input then need to find median because from median every relative's house distance is minimum distance .

3 . Now sum the subtraction of median and right sides numbers  using loop.  

4 . Again sum the subtraction of left sides  numbers and median .

5 . Here the total sum is the desired answer .


An accepted code is given below :


#include<bits/stdc++.h>
using namespace std;

int main()
{
    long long int t,a,b,arr[1000]={0},sum;

    scanf("%lld",&t);

    while(t>0)
    {
        sum=0;

         scanf("%lld",&a);

         for(int i=0;i<a;i++)
         {
             scanf("%lld",&arr[i]);
         }

         sort(arr,arr+a);

         if(a%2!=0)
         {
             b=arr[a/2];
         }
         else
         {
             b=arr[a/2];
         }

         for(int i=a/2+1;i<a;i++)
         {
             sum=sum+abs(arr[i]-b);
         }

         for(int i=a/2-1;i>=0;i--)
         {
             sum=sum+abs(b-arr[i]);
         }

         printf("%lld\n",sum);

        t--;
    }

    return 0;

}