序言（AcWing104.货仓选址）
在一条数轴上有 n家商店，它们的坐标分别为 A1∼An。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
假设货仓的位置为x，那么问题就转化为了求|a1-x|+|a2-x|+……+|an-x|的最小值。那么这个问题就很简单，在初一学过，只要将x取在a1~an的中位数上即可。
你以为事情就这么简单？不！这个问题还要在很多难题中得到应用。
1.二维货仓选址（AcWing 123.士兵）
本题很明显要先在y轴上使用货仓选址的公式，那么，x轴上怎么办呢？当然也要将其转化为货仓选址问题。但是并不是直接使用公式。所以我们要思考一下：假设第一个士兵移到了一个位置上，其横坐标为x。那么移动步数为|x[1]-x|。同理第二个士兵要移动|x[2]-x-1|步，第三个移动|x[3]-x-2|步，以此类推，第n个要移动|x[n]-x-(n-1)|=|x[n]-n+1-x|。那么很明显，我们只要将所有的a[i]=x[i]-i+1排序求中位数即可。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=10005;
int a[N],b[N];
int main(){
int n;
long long ans=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
a[i]-=i;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
ans+=abs(a[i]-a[n+1>>1]);
ans+=abs(b[i]-b[n+1>>1]);
}
cout<<ans<<endl;
}
2.推公式转化（AcWing122.糖果传递）
凡是碰到环形类问题，都要想到拆环为链的思想，那么我们想一下链状的糖果传递怎么做呢？很明显是从左向右不断地传递就可以了。所以对于该问题，设给定的糖果数为a1~an，设a为整个数组中的数字的平均数，那么ans=|a1-a|+|a1+a2-2a|+|a1+a2+a3-3a|+……+|a1+a2+a3+……+an-na|。但这个式子并不是我们想要的形式，所以要对它变形：根据拆环为链的思想，我们应当去枚举断开的位置，但是这样的复杂度达到了O(n^2)，不能接受。所以我们可以假设拆开后的链的第一个数是原数组的第k个数ak。那么式子就变成了：|ak-a|+|ak+1 + ak+2 -2a|+……+|ak+ak+1 + ak+2 +……+an- (n-k) * a|+|ak+ak+1 + ak+2 +……+an+a1- (n-k+1) * a|+……+|ak+ak+1 + ak+2 +……+an+a1+……+ak-1 -na|，那么到这里，我们注意到每一项中ai的个数与a的系数相同，可以将它们配对。那么配对后可以发现这其中的每一项都是原数组中的一段区间和，考虑采用前缀和：令b[i]=a[i]-a，f[i]为b[i]的前缀和数组。那么式子可以化为：|f[k]-f[k-1]|+|f[k+1]-f[k-1]|+……+|f[n]-f[k-1]|+|f[n]-f[k-1]+f[1]|+|f[n]-f[k-1]+f[2]|+……+|f[n]-f[k-1]+f[k-1]|。我们惊奇地发现：所有的项中都有-f[k-1]，好像可以用公式了，但是后面还有f[n]怎么办？显然f[n]=0。至此，这个问题被完美地解决了。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+5;
typedef long long ll;
ll a[N],f[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
a[0]+=a[i];
}
a[0]/=n;
for(int i=1;i<=n;i++){
a[i]-=a[0];
f[i]+=f[i-1]+a[i];
}
sort(f+1,f+n+1);
ll ans=0;
for(int i=1;i<=n;i++){
ans+=abs(f[i]-f[n+1>>1]);
}
cout<<ans<<endl;
}
总结：求解这一类问题，一定要对一些基本的转化思想与模板题了然于胸，并且对数学有一定的敏感程度。