距离之和最小

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

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

Output
输出最小距离之和

Sample Input

5
-1
-3
0
7
9

Sample Output

20

水题，求绝对值函数最小值。数轴图像分析，某动点与两定点距离之和最小当且仅当动点在定点之间（绝对值不等式），推而广之，某动点与一堆定点距离之和最小当且仅当动点两侧定点数相同（奇数个定点时动点可以在中间定点上），问题解决。

#include<iostream>
#include<algorithm>

using namespace std;

int n1[10005],n2[10005];

int main()
{
    int n;
    long long sum=0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>n1[i];
    sort(n1,n1+n);
    for(int i=n-1;i>=0;i--)
        n2[n-1-i]=n1[i];
    for(int i=0;n1[i]<n2[i];i++)
        sum+=n2[i]-n1[i];
    cout<<sum<<endl;
    return 0;
}

最后

以上就是知性小丸子为你收集整理的距离之和最小距离之和最小的全部内容，希望文章能够帮你解决距离之和最小距离之和最小所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。