货仓选址

如果是个明眼人，可以看出来选中位数一定是最优解，此时答案一定是后一半的和减去前一半的和，即${\sum }_{i=1}^{n\mathrm{/}2}(v_{n-i+1}-v_i)\backslash sum\_\{i=1\}^\{\{n\}/\{2\}\}(v\_\{n-i+1\}-v\_i)$。

但是像我这样的大制杖就只能硬证。。。

我们求的是：

$\min f(x)={\sum }_{i=1}^n\mathrm{\mid }x-v_i\mathrm{\mid }\backslash min\; f(x)=\backslash sum\_\{i=1\}^n|x-v\_i|$

这个最小的取值和下面这个式子一定是一样的：

$\min g(x)={\sum }_{i=1}^n(x-v_i{)}^2\backslash min\; g(x)=\backslash sum\_\{i=1\}^n(x-v\_i)^2$

这个式子化起来很简单了对吧：

$g(x)=n(x-\frac{{\sum }_{i=1}^n{v}_i}{n})+Constg(x)=n(x-\backslash frac\{\backslash sum\_\{i=1\}^nv\_i\}\{n\})+Const$

所以令$x=\frac{{\sum }_{i=1}^n{v}_i}{n}x=\backslash frac\{\backslash sum\_\{i=1\}^nv\_i\}\{n\}$即可，算出来的最后答案也是${\sum }_{i=1}^{n\mathrm{/}2}(v_{n-i+1}-v_i)\backslash sum\_\{i=1\}^\{\{n\}/\{2\}\}(v\_\{n-i+1\}-v\_i)$。

记得$longlonglong\backslash \; long$。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
using namespace std;
int n,a[MAXN];
long long ans=0;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
	return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
void solve(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+n+1);
    for(int i=1;i<=(n>>1);i++)ans+=a[n-i+1]-a[i];
    printf("%lld\n",ans);
}
int main(){
    solve();
    return 0;
}