杭電2083(簡易版の最短距離)
7191 ワード
簡易版の最短距離
Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 2 Accepted Submission(s) : 2
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
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
Sample Output
//観察によると、最も短い時間がほしいのは、ソートされた配列要素の中間値を<アクセス開始>で比較するだけであることが分かった;//nのパリティを判断しないのは本当ですか?しばらく知らない;
//水のほうが健康です.
Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 2 Accepted Submission(s) : 2
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
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
//観察によると、最も短い時間がほしいのは、ソートされた配列要素の中間値を<アクセス開始>で比較するだけであることが分かった;//nのパリティを判断しないのは本当ですか?しばらく知らない;
1 #include<cstdio>
2 #include<algorithm>
3 using namespace std;
4
5 int zhengzhi(int a,int b)
6 {
7 if(a-b<0)
8 return b-a;
9 else
10 return a-b;
11 }
12
13 int main()
14 {
15 int m;
16 scanf("%d",&m);
17 while(m--)
18 {
19 int n,i,sum=0,sum1=0,num[500];
20 scanf("%d",&n);
21 for(i=0;i<n;i++)
22 scanf("%d",&num[i]);
23 sort(num,num+n);
24 if(n%2==1) // ;
25 {
26 for(i=0;i<n;i++)
27 sum+=zhengzhi(num[i],num[(n-1)/2]);
28 }
29 else
30 {
31 for(i=0;i<n;i++)
32 {
33 sum1+=zhengzhi(num[i],num[n/2]);
34 sum+=zhengzhi(num[i],num[n/2-1]);
35 }
36 if(sum1>sum)
37 sum=sum1;
38 }
39 printf("%d
",sum);
40 }
41 return 0;
42 }
//水のほうが健康です.