HDU 2083 简易版之最短距离

解题报告：在一条直线上，找出一个点，求这个点到其它所有的点的距离之和，输出这个和。

可以确定这个点一定是所有的点的中位数，如果个数是偶数个的话，看中位数更接近中间两个的哪一个，取更接近的那一个。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cmath>
 6 using namespace std;
 7 const int maxn = 500+3;
 8 double A[maxn];
 9 int N;
10 int main() {
11     int  T;
12     scanf("%d",&T);
13     while(T--) {
14         scanf("%d",&N);
15         for(int i = 0;i<N;++i)
16         scanf("%lf",&A[i]);
17         sort(A,A+N);
18         int M;
19         if(N & 1) M = A[N/2];
20         else {
21             double x = (A[N/2-1] + A[N/2])/2;
22             M = (abs(A[N/2-1]-x) < abs(A[N/2]-x))? A[N/2-1]:A[N/2];
23         }
24         int tot = 0;
25         for(int i = 0;i<N;++i)
26         tot += abs(A[i]-M);
27         printf("%d
",tot);
28     }
29     return 0;
30 } 
31

View Code