「Bzoj 3170」「Tjoi2013」松鼠聚会(切比雪夫距离转曼哈顿距离)

bzoj 3170
题意：有$N$个小松鼠，它们的家用一个点$x,y$表示，两个点的距离定义为：点$(x,y)$和它周围的$8$个点即上下左右四个点和对角的四个点，距离为$1$。现在$N$个松鼠要走到一个松鼠家去，求走过的最短距离。

只走八个方向的距离为切比雪夫距离。
切比雪夫距离转曼哈顿距离：将原来的$(x,y)$转化为$(x+y,x-y)$
曼哈顿距离转切比雪夫距离：将原来的$(x,y)$转化为$(\frac{x+y}{2},\frac{x-y}{2})$
可用曼哈顿的展开式证明

所以这题转化以后，就变为了求一个点到其他点的曼哈顿距离和最小是多少。
考虑枚举这个点，然后分别对于$x,y$拆绝对值式子算值，然后取$\min$即可。这里要先将坐标转化为$(x+y,x-y)$，然后最后答案除以二即可。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 100000 + 5;

    struct xx {
        LL x, pos;
        bool operator < (const xx &rhs) const {return x < rhs.x;}
    } x[MAXN];
    struct yy {
        LL y, id;
        bool operator < (const yy &rhs) const {return y < rhs.y;}
    } y[MAXN];

    LL n, pre_x[MAXN], pre_y[MAXN];

    void clean() {
        ms(pre_x, 0), ms(pre_y, 0);
    }
    int solve() {

        clean();
        scanf("%lld", &n);
        for (LL i = 1; i <= n; ++i) {
            scanf("%lld%lld", &x[i].x, &y[i].y);
            LL tmp1 = x[i].x + y[i].y, tmp2 = x[i].x - y[i].y;
            x[i].x = tmp1, y[i].y = tmp2;
            y[i].id = i;
        }
        sort(y + 1, y + 1 + n);
        for (LL i = 1; i <= n; ++i) x[y[i].id].pos = i;
        sort(x + 1, x + 1 + n);

        for (LL i = 1; i <= n; ++i) 
            pre_x[i] = pre_x[i - 1] + x[i].x,
            pre_y[i] = pre_y[i - 1] + y[i].y;

        LL ans = 2223372036854775808ll; 
        for (LL p = 1; p <= n; ++p) {
            LL tmp1 = p * x[p].x - pre_x[p];
            tmp1 += pre_x[n] - pre_x[p] - (n - p) * x[p].x;
            LL py = x[p].pos;
            LL tmp2 = py * y[py].y - pre_y[py];
            tmp2 += pre_y[n] - pre_y[py] - (n - py) * y[py].y;

            tmp1 += tmp2;
            ans = min(ans, tmp1);
        } 

        cout << ans / 2ll;

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}