BZOJ3170: [Tjoi2013]松鼠聚会(切比雪夫距离转曼哈顿距离)
程序员文章站
2022-05-04 13:11:20
Description 有N个小松鼠,它们的家用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点即上下左右四个点和对角的四个点,距离为1。现在N个松鼠要走到一个松鼠家去,求走过的最短距离。 有N个小松鼠,它们的家用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点即 ......
Submit: 1524 Solved: 803
[][][]
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
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
Sample Output
20
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 + 10; const LL INF = 1e18 + 10; inline int read() { char c = getchar();int x = 0,f = 1; while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = x * 10 + c - '0',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 - 1]; } LL QueryY(int l, int r) { return sumy[r] - sumy[l - 1]; } LL calc(LL k) { LL posx = lower_bound(sortx + 1, sortx + N + 1, x[k]) - sortx, posy = lower_bound(sorty + 1, sorty + N + 1, y[k]) - sorty; return posx * sortx[posx] - QueryX(1, posx) - (N - posx) * sortx[posx] + QueryX(posx + 1, N) + posy * sorty[posy] - QueryY(1, posy) - (N - posy) * sorty[posy] + QueryY(posy + 1, N); } int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif N = read(); for(int i = 1; i <= N; i++) { int a = read(), b = read(); x[i] = sortx[i] = a + b, y[i] = sorty[i] = a - b; } sort(sortx + 1, sortx + N + 1); sort(sorty + 1, sorty + N + 1); for(int i = 1; i <= N; i++) sumx[i] = sumx[i - 1] + sortx[i], sumy[i] = sumy[i - 1] + sorty[i]; LL ans = INF; for(int i = 1; i <= N; i++) ans = min(ans, calc(i)); printf("%lld", ans >> 1); return 0; }