大家都知道中位数是最优解，这里给个证明。

前置：绝对值的几何意义：$|a,b|$ 为数轴上 $a$ 对应点到 $b$ 对应点的距离。

推论：$|a-x|+|x-b| \le |a+b|$ ，等号当且仅当 $a \leq b$ 时取等。（易证）

设 $n$ 个数已经被存储在 $a_1 - a_n$ 中，并且已经排过了序。

若 $n$ 为偶数，

$$\sum_{i=1}^{n} |a_i-a_t| = \sum_{i=1}^{n/2} |a_i-a_t|+|a_{n-i}-a_t|$$

$$\le \sum_{i=1}^{n/2}|a_{n-i}-a_i|$$

等号当且仅当 $t=n/2$ 或 $t=n/2+1$ 时取得。

易证若将 $t$ 往反着最优解移动（不妨设为左移至上一个点，此时 $t \le n/2$），由于移动方向上接着的数（都可以缩短 $a_t-a_{t-1}$ 的路程）小于移动方向反面的数（都可以增加 $a_t-a_{t-1}$ 的路程），这种取法一定不会比当前更优。

最优性得证。

$n$ 为奇数基本一致，只是配对部分省去中间一个数再前后配对，易证此时最优的 $t=(n+1)/2$。

综上，$t=\lfloor (n+1)/2 \rfloor$ 为最优解。

题目描述

在一条直线道路上有多个住户，现在想在这条直线道路上开一家超市，超市可以开在任何位置，包括住户所在的位置。现在请你编程求解，超市开在哪里，可以使所有住户到商店的距离的总和是最小的。

看完感受：把超市开在住户家里，也太邪恶人性化了。

言归正传，题目背景摆明了本题考查贪心思想

证明贪心策略比较简单，在升序排列中第 (n+1)>>1 项。

距离公式为 |a-b| (求a,b两地间的距离)

代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005],n,sum;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    sort(a+1,a+n+1);
    int x=a[(n+1)>>1];
    for (int i=1;i<=n;i++)
    {
        sum+=abs(x-a[i]);//这里就是上文提到的距离公式
    }
    cout << sum;
    return 0;
}

sort(a+1,a+n+1);
for (int i=1;i<=n;i++)
{
    ans+=abs(a[(n+1)/2]-a[i]);
}
cout<<ans;

#include <bits/stdc++.h>
using namespace std;
int a[100001];//注意了
int main(){   
    int n,mid=0,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    if(n%2==0){
        mid=a[n/2];//详情请看梓璇
    }else{
        mid=a[(n+1)/2];
    }
    for(int i=1;i<=n;i++){
        ans+=abs(mid-a[i]);//学过初一上学期的绝对值的人都知道
    }cout<<ans;
    return 0;
}//不对出来打我

鼓励大家写题解，但注意题解格式。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

排序挺费时间的。二分更快更电脑。