51nod 1096 距离之和最小思维题，求中位数

题目：

在一条直线上，与两个点距离之和最小的点，是怎样的点？

很容易想到，所求的点在这两个已知点的中间，因为两点之间距离最短。

在一条直线上，与三个点距离之和最小的点，是怎样的点？

由两个点的规律，我们可以想到，所求点一定夹在这些点中间。

例如： -3 0 10

我们先试探一下

取点0： |0-3|+|0-0|+|0-10| = 3+0+10 = 13

取点-1： |-1-(-3)|+|-1-0|+|-1-10| = 2+1+11 = 3+1+10 = 14

取点1 : |1-(-3)|+|1-0|+|1-10| = 4+1+11 = 3+1+10 = 14

取点-3: |-3-(-3)|+|(-3)-0|+|-3-10| = 0+3+13 = 3+3+10 = 16

取点10: |10-(-3)|+|10-0|+|10-10| = 13+10+0 = 3+10+10 = 23

我们可以观察到取点0时结果最小，取其他点会多算一些部分。

我们可以想到取中间的点的时候，距离最小。

如果有偶数个点的话，取介于中间两个点的任何一个点即可。左闭右闭[]。

这个从两个点的时候就可以看出端倪。

如果还是不清楚的话，多画几个图就出来了。

代码：

#include <bits\stdc++.h>

using namespace std;

typedef long long ll;

int n; 

int a[];

int main() {

  int n;

  cin >> n;

    for(int i = ;i <= n; i++){

        cin >> a[i];

    }

    sort(a+,a+n+);

    //如果n是奇数，index表示中间的点.

    //如果是偶数，则表示中间两点中右边的那个点 。

    int index = n/+;  

    ll ans = ;

    for(int i = ;i <= n; i++){

        ans += abs(a[i]-a[index]);

    }

    cout << ans << endl;

  return ;

}

巴特西

51nod 1096 距离之和最小思维题，求中位数

最新文章

热门文章

巴特西

51nod 1096 距离之和最小 思维题，求中位数

最新文章

热门文章

51nod 1096 距离之和最小思维题，求中位数