HDoj簡易版の最短距離2083(中位数を取る)水

簡易版の最短距離
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 15746    Accepted Submission(s): 6979
Problem Description
冬休みの时、ACBOYは多くの友达を访问して、ちょうど彼のすべての友达の家はすべて座標平面のX軸の上にあります.ACBOYは友人の家を任意に選んで訪問を開始することができるが、訪問するたびに出発点に戻らなければならず、次の友人を訪問することができない.
例えば4人の友人がいて,対応するX軸座標はそれぞれ1,2,3,4である.ACBOYが座標が2の点を出発点として選択した場合、彼が最終的に必要とする時間は|1-2|+|2-2|+|3-2|+|4-2|=4である.
今N人の友达の座標を与えて、それではACBOYはどのように歩いてやっと時間が最も少ないことができますか?
 
Input
入力は、まず正の整数Mであり、M個のテストインスタンスを表す.各例の入力は2行あり、まず正の整数N(N<=500)であり、N人の友人がいることを示す、次の行はN個の正の整数であり、具体的な座標(すべてのデータが<=10000)を示す.
 
Output
各テストインスタンスについて、すべての友人にアクセスするのにかかる最小時間を出力し、各インスタンスの出力が1行を占めます.
 
Sample Input

   
   
   
   

    
    
    
    2
2 
2 4 
3 
2 4 6
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    2
4
   
   
   
   
   
   
   
   

    
    
    
    
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
#define ll long long
#define IN __int64
#define N 1010
#define M 1000000007
using namespace std;
int a[N];
int main()
{
	int t,n,i,j,k;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		sort(a,a+n);
		int p=n/2;
		int sum=0;
		for(i=0;i<n;i++)
		{
			sum+=abs(a[i]-a[p]);
		}
		printf("%d
",sum);
	}
	return 0;
}