51nod 1096 距离之和最小 (中位数）

分析：按位置升序排列，找出中位数，求出中位数到各点距离即可。注意用long long。

　　　为什么是中位数？假设排好序后的点为a、b、c、d、e.找一点x满足到这五个点距离和最小，要想到a和e（区间两端点）距离和最小，则x点一定在a和e之间。

　　　同理，要到b和d距离和最小，x点一定在b和d之间。最后，要到c点距离最小，那么x点一定与c点重合。所以，x点是中位数。

代码：

 1 #include <iostream>
 2 #include <cmath>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 ll a[10005];
 7 int main()
 8 {
 9     ios::sync_with_stdio(false);
10     ll n;
11     cin>>n;
12     for(ll i=0;i<n;i++)
13         cin>>a[i];
14     sort(a,a+n);
15     ll ans=0;
16     ll tmp=n>>1;  //其实就是n/2
17     for(ll i=0;i<n;i++)
18         ans+=fabs(a[tmp]-a[i]);
19     cout<<ans<<endl;
20 }

View Code

1096 距离之和最小

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

关注

取消关注

X轴上有N个点，求X轴上一点使它到这N个点的距离之和最小，输出这个最小的距离之和。

Input

第1行：点的数量N。(2 <= N <= 10000)
第2 - N + 1行：点的位置。（-10^9 <= P[i] <= 10^9)

Output

输出最小距离之和

Input示例

Output示例