杭電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
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 }

//水のほうが健康です.