P3964 [TJOI2013] 松鼠聚会

题意

给定 \(n\) 个点，求出一个点使得每个点到这个点的切比雪夫距离之和最小。

思路

首先，我们可以把题目中的切比雪夫距离转化为曼哈顿距离，因为我们知道形如 \((x, y)\) 点之间的曼哈顿距离等于 \((x + y, x - y)\) 点之间的切比雪夫距离，\((x, y)\) 点之间的切比雪夫距离等于 \(\left(\dfrac{x + y}{2}, \dfrac{x - y}{2}\right)\) 点之间的曼哈顿距离。所以我们可以先将这些点转化一下，用曼哈顿距离进行计算。

然后，题目转化为找到所有点到一个点的曼哈顿距离之和最小，所以我们先将 \(x, y\) 数组排序，然后分开考虑，设选择的点为 \(x_i\)（排序后）。

\(\sum x = (x_i - x_1) + (x_i - x_2) + (x_i - x_3) + \cdots + (x_i - x_i) + (x_{i + 1} - x_i) + (x_{i + 2} - x_i) + \cdots + (x_n - x_i) = i\cdot x_i - (n - i) x_i - \sum\limits_{j = 1}^{i}x_j + \sum\limits_{j = i + 1}^{n}x_j\)

\(y\) 同理，然后我们对于原坐标，用二分对应到排序后的数组，然后根据公式求出答案。

代码

为了避免小数，我们将所有的数字先乘以 2，然后在输出距离时，将距离 / 2。

#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

const int N = 100010;

i64 n, x[N], y[N], cx[N], cy[N], sx[N], sy[N];

i64 sum(i64 a[], int l, int r) {
    if (l > r) return 0;
    return a[r] - a[l - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        x[i] *= 2, y[i] *= 2;
        i64 a = (x[i] + y[i]) / 2, b = (x[i] - y[i]) / 2;
        cx[i] = x[i] = a, cy[i] = y[i] = b;
    }

    sort(x + 1, x + n + 1);
    sort(y + 1, y + n + 1);
    for (int i = 1; i <= n; i++) sx[i] = x[i] + sx[i - 1];
    for (int i = 1; i <= n; i++) sy[i] = y[i] + sy[i - 1];
    i64 ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= n; i++) {
        i64 mx = cx[i], my = cy[i];
        int px = lower_bound(x + 1, x + n + 1, mx) - x;
        int py = lower_bound(y + 1, y + n + 1, my) - y;
        i64 ans_x = px * mx - (n - px) * mx - sum(sx, 1, px) + sum(sx, px + 1, n);
        i64 ans_y = py * my - (n - py) * my - sum(sy, 1, py) + sum(sy, py + 1, n);
        ans = min(ans, ans_x + ans_y);
    }
    cout << ans / 2 << '\n';
    return 0;
}