Hdu 4312-Meeting point-2——哈夫曼距离与切比雪夫距离

题意

从 $n$ 个点中选择一点，使得其他点到其的切比雪夫距离最小（$0 < n \leq 1e5$）.

分析

定理：$(x_1, y_1)$ 与 $(x_2, y_2)$ 的曼哈顿距离等于 $(x_1-y_1, x_1+y_1)$ 与 $(x_2-y_2, x_2+y_2)$ 的切比雪夫距离。

转换成曼哈顿距离中的坐标，求曼哈顿距离。

由于这个点必须是 $n$ 个点中的一点，所以 $x,y$ 还有限制关系（不然直接排序取中点就完事了）。

我们对分别对 $x,y$ 排序并求出前缀和，

然后枚举这 $n$ 个点，对于每个点，可以 $O(log n)$ 得到 $x$ 方向和 $y$ 方向的绝对值之和，两者相加即是答案。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = (1LL) << ;

const int maxn = 1e5 + ;

int n, x[maxn], y[maxn], sx[maxn], sy[maxn];;

ll sum_x[maxn], sum_y[maxn];

struct Node{

    int x, y, id;

}p[maxn];

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &n);

        for(int i = ;i <= n;i++)

        {

            int a, b;

            scanf("%d%d", &a, &b);

            x[i] = sx[i] = a+b; y[i] = sy[i] = b-a;;   //为了保证为整数，扩大了两倍

        }

        sort(sx+, sx+n+);

        sort(sy+, sy+n+);

        for(int i = ;i <= n;i++)

        {

            sum_x[i] = sum_x[i-] + sx[i];

            sum_y[i] = sum_y[i-] + sy[i];

        }

        ll ans = INF;

        for(int i = ;i <= n;i++)   //枚举每个点

        {

            ll px = lower_bound(sx+, sx+n+, x[i]) - sx;  //如果之前记录下来，就可以O(1)

            ll py = lower_bound(sy+, sy+n+, y[i]) - sy;

            ll tmp = px*x[i] - sum_x[px] + sum_x[n] - sum_x[px] - (n-px)*x[i];  //相乘爆int

            tmp += py*y[i] - sum_y[py] + sum_y[n] - sum_y[py] - (n-py)*y[i];

            if(tmp < ans)  ans = tmp;

        }

        printf("%lld\n", ans/);

    }

}

参考链接：https://www.cnblogs.com/SGCollin/p/9636955.html