前缀和解法
观察到所有仓库在x轴的位置上均大于0, 可以用前缀和的解法
先把所有仓库位置读入, 按坐标轴从小到大排序
如果把仓库建在第i个仓库的位置上,则第i个仓库的到1,2,3,i-1个仓库的总距离为 a[i]*(i-1) - (a[1]+…+a[i-1])
第i个仓库到i+1, i+2....n个仓库的距离之和为 a[i+1] + a[i+2] + … +a[n] - (n - i) * a[i]
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], s[N];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
int res = 0x7fffffff;
for(int i = 1; i <= n; i++){
int l = (i - 1) * a[i] - s[i - 1];
int r = s[n] - s[i] - (n - i)*a[i];
res = min(res, l + r);
}
cout << res << endl;
return 0;
}
绝对值不等式解法
一维扩展到二维:3167.星星还是树
扩展到d维:需要用模拟退火算法。
记仓库位置为x, 目前所有仓库的坐标从小到大排序后的位置为x1, x2 … xn , 直觉上,x 的选址越靠近中间距离越小
那么距离为|x - x1| + |x - x2| + .. + | x - xn |
如果n为奇数,不妨设只有三组|x - x1| + |x - x2| + | x - x3 | 所以当x = x2时必然 距离最短
如果n为偶数,不妨设只有两组|x - x1| + |x - x2| 所以当x = x2 或 x = x1 时距离最短, 均为x2 - x1
拓展到一般的情形,则x = n/2时,就是最短的距离
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
}
int res = 0;
sort(a, a + n);
for(int i = 0; i < n; i++) res += abs(a[n >> 1] - a[i]);
cout << res << endl;
return 0;
}