给定直线上 \(n\) 个点，其坐标分别为 \(x_1, x_2, \dots, x_n\)。需要在这条直线上找一个点 \(P(x)\)，使得 \(P\) 到所有已知点的绝对距离之和最小，即最小化目标函数 \(f(x) = \sum \limits_{i=1}^n |x - x_i|\)。
当 \(x\) 取这组数的大小的中位数时，\(f(x)\) 取得最小值。
考虑任意两点 \(x_i\) 和 \(x_j\)（设 \(x_i \lt x_j\)），根据几何意义，要使 \(|x-x_i| + |x-x_j|\) 最小，\(x\) 必须落在 \([x_i,x_j]\) 区间内，此时两距离之和恒等于 \(x_j - x_i\)。因此，将 \(n\) 个点从小到大排序后，首尾两两配对：
若 \(n\) 为偶数，中位数是一个区间 \([x_{n/2}, x_{n/2+1}]\)，区间内任意一点均可使距离和达到最小。
#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
int a[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
// 解决货仓选址问题的关键是找到所有坐标的中位数，并将所有点到中位数的距离相加。
// 可以使用一个更巧妙的数学技巧来直接计算最小距离和，而无需显式找出中位数。
// 1. 首先对所有坐标进行排序。
sort(a + 1, a + n + 1);
ll ans = 0;
// 2. 最小距离和等于排序后对称位置的坐标差之和。
// 这个结论的含义是 sum(|a[i] - median|) = (a[n] - a[1]) + (a[n-1] - a[2]) + ...
// 循环通过配对最远和最近、次远和次近的点，来直接累加这个总和。
for (int i = 1; i * 2 <= n; i++) {
ans += a[n - i + 1] - a[i];
}
printf("%lld\n", ans);
return 0;
}
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = (int)1e5 + 5;
int a[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
nth_element(a, a + n / 2, a + n);
int m = a[n / 2], ans = 0;
for (int i = 0; i < n; i++) {
ans += abs(a[i] - m);
}
cout << ans << "\n";
return 0;
}
在二维平面上有 \(n\) 个点 \((x_i,y_i)\)，要求找一个点 \((X,Y)\)，使得该点到所有点的曼哈顿距离之和最小，即 \(\min \sum \limits_{i=1}^n (|X-x_i| + |Y-y_i|)\)。
由于曼哈顿距离的 \(x\) 轴坐标与 \(y\) 轴坐标互不干扰，目标函数可以拆分为 \(\sum |X-x_i| + \sum |Y-y_i|\)。分别求出 \(x\) 序列的中位数 \(X\) 和 \(y\) 序列的中位数 \(Y\)，组合成 \((X,Y)\) 即为所求。
给定 \(n\) 个士兵在网格点上的坐标 \((x_i,y_i)\)，他们可以沿网格上、下、左、右移动。目标是将他们排成一个水平队列，坐标分别为 \((x,y),(x+1,y),\dots,(x+n-1,y)\)，求出最少的总移动步数。
总移动步数是每个士兵移动步数之和，由于士兵只能沿网格移动，移动步数即为曼哈顿距离 \(\sum \limits_{i=1}^n |x'_i-x_i| + \sum\limits_{i=1}^n |y'_i - y_i|\)。由于 \(x\) 方向和 \(y\) 方向的移动是独立的，可以分别求解两个维度的最小值。
最终所有士兵的纵坐标都必须是同一个值 \(y'\)，目标是最小化 \(\sum\limits_{i=1}^n |y_i - y'|\)。这是一个经典的中位数问题，根据绝对值不等式，当 \(y'\) 取 \(y_1,y_2, \dots, y_n\) 的中位数时，距离之和最小。
最终士兵的横坐标应为 \(x_s,x_s+1,\dots,x_s+n-1\)，为了使总移动步数最小，应该让初始横坐标较小的士兵排在目标队列中较靠左的位置（即排序后的第 \(i\) 个士兵对应目标位置的第 \(i\) 个坐标）。设排序后的横坐标为 \(x'_0, x'_1, \dots, x'_{n-1}\)，目标是最小化 \(\sum\limits_{i=1}^n |x'_i - (x_s+i)|\)，将公式变形，得到 \(\sum\limits_{i=0}^{n-1} |(x'_i-i)-x_s|\)。令 \(z_i=x'_i-i\)，则问题转化为最小化 \(\sum\limits_{i=0}^{n-1} |z_i-x_s|\)，这样就再次变成了一个中位数问题。
这里对 \(x\) 的排序是必须的，因为在代入 \(X'_i = X_i - i\) 这个公式前，等式右边的 \(i\) 必须严格对应升序排列后的第 \(i\) 小的士兵，因此时间复杂度为 \(O(n\log n)\)。
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = (int)1e4 + 5;
int x[N], y[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
sort(x, x + n);
for (int i = 0; i < n; i++) {
x[i] -= i;
}
nth_element(x, x + n / 2, x + n);
nth_element(y, y + n / 2, y + n);
int mx = x[n / 2], my = y[n / 2], ans = 0;
for (int i = 0; i < n; i++) {
ans += abs(x[i] - mx) + abs(y[i] - my);
}
cout << ans << "\n";
return 0;
}
如果数轴上的每个点都有一个正权值 \(w_i\)，这就是带权距离和问题，要最小化带权绝对距离之和 \(f(x) = \sum\limits_{i=1}^n w_i \cdot |x_i-x|\)。
对于一组已经按坐标从小到大排序的点 \((x_1, w_1), (x_2, w_2), \dots, (x_n, w_n)\)，令总权重为 \(W = \sum_{i=1}^n w_i\)。从左往右累加权重，当累加的权重第一次达到或超过总和的一半时，该位置对应的坐标即为带权中位数。
扰动法：假设当前选址在 \(x_k\)，若将其向右移动一个微小的距离 \(\Delta\)，则 \(x_k\) 左侧的所有点到新选址的距离都会增加 \(\Delta\)，总代价增加 \(\Delta \cdot \sum_{i=1}^k w_i\)；而 \(x_k\) 右侧的所有点到新选址的距离都会减少 \(\Delta\)，总代价减少 \(\Delta \cdot \sum_{i=k+1}^n w_i\)。要让向右移动不优（总代价不减少），必须满足 \(\sum \limits_{i=1}^k w_i \ge \sum \limits_{i=k+1}^n w_i\)。两边同时加上左边，得 \(2 \cdot \sum_{i=1}^k w_i \ge W\)，即 \(\sum_{i=1}^k w_i \ge \frac{W}{2}\)。同理可证向左移动不优的条件，因此，总权重越过半数的那个转折点就是全局最优解。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
const int N = 100005;
struct House {
ll x;
int r;
};
House a[N];
int main()
{
ll l; int n;
scanf("%lld%d", &l, &n);
int sumr = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld%d", &a[i].x, &a[i].r);
sumr += a[i].r;
}
sort(a + 1, a + n + 1, [](House &h1, House &h2) {
return h1.x < h2.x;
});
int pos = -1;
ll sum = 0;
for (int i = 1; i <= n; i++) {
sum += a[i].r;
if (pos == -1 && sum * 2 >= sumr) {
pos = i;
}
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans += abs(a[i].x - a[pos].x) * a[i].r;
}
printf("%lld\n", ans);
return 0;
}
如果采用类似快速选择的算法找加权中位数，平均时间复杂度能做到 \(O(n)\)。
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;
using ll = long long;
const int N = (int)1e5 + 5;
struct House {
ll x;
int r;
};
House a[N];
int sum(int l, int r) {
int res = 0;
for (int i = l; i <= r; i++) {
res += a[i].r;
}
return res;
}
int main()
{
ll l; int n;
cin >> l >> n;
int w = 0;
for (int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].r;
w += a[i].r;
}
ll m = -1, pre = 0, suf = 0;
int left = 0, right = n - 1;
while (left <= right) {
if (left == right) {
m = a[left].x;
break;
}
int p = left + rand() % (right - left + 1);
ll px = a[p].x;
int i = left, j = right, k = left;
// 三向切分
while (k <= j) {
if (a[k].x < px) {
swap(a[i], a[k]);
i++; k++;
} else if (a[k].x > px) {
swap(a[k], a[j]);
j--;
} else {
k++;
}
}
int ls = sum(left, i - 1), eq = sum(i, j), gt = sum(j + 1, right);
if (pre + ls > w / 2) {
right = i - 1;
suf += eq + gt;
} else if (suf + gt > w / 2) {
left = j + 1;
pre += eq + ls;
} else {
m = px;
break;
}
}
// 计算总距离
ll ans = 0;
for (int i = 0; i < n; i++) {
ans += abs(a[i].x - m) * a[i].r;
}
cout << ans << "\n";
return 0;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。