Lesson: 16
Problem: 10041
Title: Vito's Family
Difficulty Level: 1.0
Date: Jan 25, 2009
Site: UVA
Another easy problem. Main task is to find the median. How to find median ? Ok, follow me.
Let's we have a given set of integers: 2 3 1 4 7 3 5
To find the median, we first have to soft the array: 1 2 3 3 4 5 7
Then find, the middle most number, here is 3, so our median is 3.
What's the medain of these numbers 1 2 3 3 4 4 5 7 ?
Here we have a set of integers of even number of elements, 8, then which is the middle one ?
For this case, find the middle most 2 numbers, here are: 3 and 4
So median will be (3+4)/2 = 3 ( integer division)
Consider the first sample input.
2 4
two numbers are given, median is (2+ 4)/2 = 3
Now finally find the total of the difference between median and each number of input.
abs(2-3) + abs(4-3) = 1 + 1 = 2, output is 2
For the second case,
2 4 6, median is 4
Output: abs(2-4) + abs(4-4) + abs(6-4) = 2 + 0 + 2 = 4
Source Code:
1 #include<stdio.h> 2 #include<math.h> 3 #include<stdlib.h> 4 5 #define MAXN 30001 6 7 int RELATIVE[MAXN]; 8 long long DIFF,MID; 9 10 int sf(const void *a, const void *b) { 11 12 return *(int *)a - *(int *)b; 13 14 } 15 16 void COM_DIFF(int N) { 17 int i; 18 DIFF = 0; 19 for(i = 0;i<N; i ++) 20 DIFF += abs(RELATIVE[i] - MID); 21 printf("%lld\n",DIFF); 22 } 23 24 void main() { 25 26 int N,i,kase; 27 scanf("%d",&kase); 28 29 while(kase --) { 30 scanf("%d",&N); 31 32 for(i = 0;i<N; i++) 33 scanf("%d",&RELATIVE[i]); 34 qsort(RELATIVE,N,sizeof(int),sf); 35 int k = N / 2; 36 if(N % 2 == 0) 37 MID = (RELATIVE[k-1] + RELATIVE[k]) / 2; 38 else 39 MID = RELATIVE[k]; 40 COM_DIFF(N); 41 } 42 }