BZOJ3170: [Tjoi2013]松鼠聚会(切比雪夫距离转曼哈顿距离)

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1524 Solved: 803
[Submit][Status][Discuss]

Description

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

Input

第一行给出数字N，表示有多少只小松鼠。0<=N<=10^5
下面N行，每行给出x,y表示其家的坐标。
-10^9<=x,y<=10^9

Output

表示为了聚会走的路程和最小为多少。

Sample Input

6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2

Sample Output

HINT

Source

emmm，题目给出的是切比雪夫距离，我们需要转化成曼哈顿距离

对于坐标中的每个点$(x, y)$，转化为曼哈顿距离之后是$(\frac{x + y}{2}, \frac{x - y}{2})$

然后枚举一个点$k$，我们需要算的是$\sum_{i = 1}^N |x_k - x_i| + |y_k - y_i|$

暴力拆开之后发现可以用前缀和优化

代码写出来很漂亮qwq。

#include<cstdio>

#include<algorithm>

#define LL long long

using namespace std;

const int MAXN = 1e5 + ;

const LL INF = 1e18 + ;

inline int read() {

    char c = getchar();int x = ,f = ;

    while(c < '' || c > ''){if(c == '-')f = -;c = getchar();}

    while(c >= '' && c <= ''){x = x *  + c - '',c = getchar();}

    return x * f;

}

LL N, x[MAXN], y[MAXN], sortx[MAXN], sorty[MAXN], sumx[MAXN], sumy[MAXN];

LL QueryX(int l, int r) {

    return sumx[r] - sumx[l - ];

}

LL QueryY(int l, int r) {

    return sumy[r] - sumy[l - ];

}

LL calc(LL k) {

    LL posx = lower_bound(sortx + , sortx + N + , x[k]) - sortx,

        posy = lower_bound(sorty + , sorty + N + , y[k]) - sorty;

    return posx * sortx[posx] - QueryX(, posx) - (N - posx) * sortx[posx] + QueryX(posx + , N) +

           posy * sorty[posy] - QueryY(, posy) - (N - posy) * sorty[posy] + QueryY(posy + , N);

}

int main() {

#ifdef WIN32

    freopen("a.in", "r", stdin);

#endif

    N = read();

    for(int i = ; i <= N; i++) {

        int a = read(), b = read();

        x[i] = sortx[i] = a + b,

        y[i] = sorty[i] = a - b;

    }

    sort(sortx + , sortx + N + );

    sort(sorty + , sorty + N + );

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

        sumx[i] = sumx[i - ] + sortx[i],

        sumy[i] = sumy[i - ] + sorty[i];

    LL ans = INF;

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

        ans = min(ans, calc(i));

    printf("%lld", ans >> );

    return ;

}

秒客网