104. 货仓选址

首先将数组(a)从小到大排序。

[|a_1-x|+|a_2-x|+cdots+|a_n-x| ge|a_n-a_1|+|a_{n-1}-a_2|+cdots +|a_{n/2+1}-a_{n/2}| ]

当(x)位于(a_n)和(a_1)之间时，(|a_1-x|+|a_n-x| ge |a_n-a_1|)，依次类推，当(x)位于所有数的中位数上时，上式等号成立。

• (n)是奇数，(x)选在中位数位置
• (n)是偶数，(x)选在中间两个数之间任意一个位置均可

const int N = 1e5+10;
int a[N];
int n;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    
    int mid=a[n/2];
    int res=0;
    for(int i=0;i<n;i++) res+=abs(a[i]-mid);
    cout<<res<<endl;
    
    return 0;
}