【原題】
Background
The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them.
Problem
Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem.
Input
The input consists of several test cases. The first line contains the number of test cases.
For each test case you will be given the integer number of relatives r ( 0 < r < 500) and the street numbers (also integers) where they live ( 0 < si < 30000 ). Note that several relatives could live in the same street number.
Output
For each test case your program must write the minimal sum of distances from the optimal Vito's house to each one of his relatives. The distance between two street numbers si and sj is dij= |si-sj|.
Sample Input
2
2 2 4
3 2 4 6
Sample Output
2
4
【題目大意】
一個黑社會老大要搬家到紐約的某一條街上， 他在那條街上有很多的親戚朋友，要找到一個地方，使得這個地方走到所有親戚朋友家的總距離最短。
【分析與總結】
赤裸裸的找中位數就OK了...
【代碼】
[cpp]
/*
* UVa: 10041 Vito's Family
* Time: 0.024s
* Author: D_Double
*
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 510
using namespace std;
int arr[MAXN], n;
void solve(){
sort(arr, arr+n);
if(n&1){ //如果是奇數，一定是正中間那個數
int mid=arr[(n-1)>>1];
int sum=0;
for(int i=0; i<n; ++i)
sum += abs(arr[i]-mid);
printf("%d\n",sum);
}
else{ //如果是偶數，那麼是中間兩個之和的一半
int mid=(arr[(n-2)>>1]+arr[n>>1])/2;
int sum=0;
for(int i=0; i<n; ++i)
sum += abs(arr[i]-mid);
printf("%d\n", sum);
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0; i<n; ++i)
scanf("%d",&arr[i]);
solve();
}
return 0;
}
