「Luogu P3964」「TJOI2013」松鼠聚会

Description

给定 $n$ 个点,每个点的坐标为 $(x_i,y_i)$,且点 $(x,y)$ 到它周围 $8$ 个点

$(x-1,y)(x+1,y),(x,y-1),(x,y+1).(x-1,y+1),(x-1,y-1),(x+1,y+1),(x+1,y-1)$

的距离均为 $1$ 。现要找到一个点,使其它点到这个点的距离和最小,输出这个最小值。

$(0 \leq n \leq 10^5,-10^9 \leq x_i,y_i \leq 10^9)$

Source

[Luogu]P3964

Solution

很容易看出这道题属于 切比雪夫距离 的一般模型。即对于两个点 $(x_1, y_1),(x_2,y_2)$,它们之间的距离为

直接求 切比雪夫距离 似乎很困难?考虑把 切比雪夫距离 转化为 曼哈顿距离,即把每个点的坐标 $(x,y)$ 变为 $(\frac{x + y}{2}, \frac{x - y}{2})$ 。(详见 常用距离算法详解

枚举所选的点 $i$,我们只需要计算其它点到它的曼哈顿距离和即可。

如果某个点 $j$ 的横坐标 $x_j \leq x_i$,则它的对总距离的贡献为 $x_i - x_j$,反之则为 $x_j - x_i$ 。

这样就可以分两种情况讨论了。

设前 $k$ 个点的横坐标都 $\leq x_i$,那么所有点横坐标的贡献和为

对于 $\sum\limits_{i = 1}^k x_i$ 和 $\sum\limits_{i = k+1}^n x_i$,我们可以预处理出 $x$ 的前缀和后 $O(1)$ 求得。

怎么求 $k$ 呢?显然可以将横坐标排序后二分得到。

纵坐标 $y$ 的计算方法与上面一样。时间复杂度为 $O(n \log n)$ 。

切比雪夫距离 转成 曼哈顿距离 时要除以 $2$,为了避免出现小数,我们可以横坐标和纵坐标同时乘上 $2$,最后答案除以 $2$ 。

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
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5;
int n, x[MAXN + 5], y[MAXN + 5], p[MAXN + 5], q[MAXN + 5];
LL ans = 0x7fffffffffffffff, prex[MAXN + 5], prey[MAXN + 5];

int main() {
read(n);
for (int a, b, i = 1; i <= n; ++i) {
read(a), read(b);
x[i] = p[i] = a + b, y[i] = q[i] = a - b;//转曼哈顿距离,且乘上 2
}
sort(p + 1, p + n + 1), sort(q + 1, q + n + 1);//排序
for (int a, b, i = 1; i <= n; ++i)//维护前缀和
prex[i] = prex[i - 1] + p[i], prey[i] = prey[i - 1] + q[i];
for (int posx, posy, i = 1; i <= n; ++i) {
posx = lower_bound(p + 1, p + n + 1, x[i]) - p;
posy = lower_bound(q + 1, q + n + 1, y[i]) - q;
//二分找到 x[i] 和 y[i] 是所有点中第几个大的
LL sumx, sumy;
sumx = (LL) posx * x[i] - prex[posx] +
prex[n] - prex[posx] - (LL) (n - posx) * x[i];//计算横坐标贡献
sumy = (LL) posy * y[i] - prey[posy] +
prey[n] - prey[posy] - (LL) (n - posy) * y[i];//计算纵坐标贡献
ans = min(ans, sumx + sumy);
}
write(ans / 2);//答案不要忘记除回去
putchar('\n');
return 0;
}

本文标题:「Luogu P3964」「TJOI2013」松鼠聚会

文章作者:Heartlessly

发布时间:2019年06月19日 - 07:21:03

最后更新:2019年06月28日 - 09:05:02

原始链接:https://heartlessly.github.io/problems/luogu-p3964/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%