HDoj 2083簡易版の最短距離

1736 ワード

簡易版の最短距離
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 13510    Accepted Submission(s): 6000
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>
using namespace std;
bool cmp(int a,int b)
{
	return a<b;
}
int main()
{
	int n,m,j,i,s,t,sum;
	int a[1100];
	scanf("%d",&n);
	while(n--)
	{	
		scanf("%d",&m);
		sum=0;s=0;
		for(i=0;i<m;i++)
		scanf("%d",&a[i]);	
		sort(a,a+m,cmp);	    
		if(m%2!=0)
		{
			s=(m-1)/2;		    
		    for(i=0;i<m;i++)
		    {
			    sum+=abs(a[i]-a[s]);
		    }   
	    }
		else
		{
			s=m/2-1;
			for(i=0;i<m;i++)
		    {
			    sum+=abs(a[i]-a[s]);
		    }
		}				    
		printf("%d
",sum); sum=0; } return 0; }