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
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;
}