BZOJ 3170: [Tjoi 2013]松鼠聚会

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

-4 -1

-1 -2

2 -4

0 2

0 3

5 -2

Sample Output

Solution

排序+乱搞。

这道题就是要求\(\min_{1 \le i \le n} \{\sum _{1 \le j \le n} {dis_{i,j}}\}\)的i。

其中\(dis_{i,j}=\max(|x_i-x_j|,|y_i-y_j|)\)

而\(|x_i-x_j|\)和\(|y_i-y_j|\)都是自然数，因此

\begin{eqnarray}

& & \max (|x_i-x_j|,|y_i-y_j|) \

& = & \frac{|(x_i-x_j)+(y_i-y_j)|+|(x_i-x_j)-(y_i-y_j)|}{2} \

& = & \frac{|(x_i+y_i)-(x_j+y_j)|+|(x_i-y_i)-(x_j-y_j)|}{2}

\end{eqnarray}

我们可以先预处理出来所有\(x_i+y_i\)、\(x_i-y_i\)，然后对于这两个分别排序（便于计算i处答案），然后记录一下前缀和和后缀和，扫一遍统计每个i的答案，取最小值即可。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL LINF = ~0uLL >> 1;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int x, y;
const int maxn = 100005;
int N;
LL pre[maxn], suc[maxn], disX[maxn], disY[maxn];
struct Node { LL X, Y; int id; } p[maxn];
bool cmpX(Node a, Node b) { return a.X < b.X; }
bool cmpY(Node a, Node b) { return a.Y < b.Y; }
int main() {
    N = getint();
    for (int i = 1; i <= N; ++i) {
        x = getint(); y = getint();
        p[i].X = (x + y);
        p[i].Y = (x - y);
        p[i].id = i;
    }
    sort(p+1, p+N+1, cmpX);
    for (int i = 1, j = N; i <= N; ++i, --j) {
        pre[i] = pre[i - 1] + p[i].X;
        suc[j] = suc[j + 1] + p[j].X;
    }
    for (int i = 1; i <= N; ++i)
        disX[p[i].id] = p[i].X * (i - 1) + suc[i + 1] - pre[i - 1] - p[i].X * (N - i);
    sort(p+1, p+N+1, cmpY);
    for (int i = 1, j = N; i <= N; ++i, --j) {
        pre[i] = pre[i - 1] + p[i].Y;
        suc[j] = suc[j + 1] + p[j].Y;
    }
    for (int i = 1; i <= N; ++i)
        disY[p[i].id] = p[i].Y * (i - 1) + suc[i + 1] - pre[i - 1] - p[i].Y * (N - i);
    LL ans = LINF;
    for (int i = 1; i <= N; ++i)
        ans = min(ans, disX[i] + disY[i]);
    ans >>= 1;
    printf("%lld", ans);
    return 0;
}