题解 50937 货仓选址

题目链接

假设把货仓建在第k个商店的坐标上，那么左边有 k - 1 个商店，右边有 n - k - 1 个商店。

当k<n/2时，向右移一位，因为k-1<n-k-1，所以+(k-1)-(n-k-1)会使总距离减小，因此我们应当把k往右移，直到当 k-1 = n-k-1时，若再往右移，k-1>n-k-1，+(k-1)-(n-k-1)会使总距离变大，所以不能往右移了。 若k-1 = n-k-1, 那么k=n/2, k也就是整个序列中位数的位置。

如果商店数为偶数的话，中点有两个商店，此时在这两个商店之间任选一点都可，即a[n/2]<=k<=a[n/2+1]，因为除这两个商店外左右两边的商店数是相等的（即k向右移总距离加减数相等），而这两个商店到k的距离和又是定值，所以不影响答案，我们可以直接选择a[n/2]。

#include<algorithm>
#include<cstdio>
using namespace std;
int n,ans,mid,a[100005];
int main() {
    scanf("%d",&n);
    for (int i=1; i<=n; i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1),mid=a[n/2];
    for (int i=1; i<=n; i++) ans+=abs(a[i]-mid);
    printf("%d",ans);
}