题链
题意：给定$n$个点，从中选择一个点$poi$，使得其他点到$x$的切比雪夫距离之和最小；
学习有关二维坐标系上有关曼哈顿距离与切比雪夫距离相互转化后；
可将题给求切比雪夫距离转化成求曼哈顿距离，相当于改变题意；
也就是说题意可变成 “ 给定$n$个点，从中选择一个点$x$，使得其他点到$poi$的曼哈顿距离之和最小 ”；
可通过枚举每一个点作为$poi$，求其他点到x的曼哈顿距离之和；
由于曼哈顿距离的性质，可将x方向上的坐标和y方向上的坐标分离，分别求其他点与$poi$的$x$方向上的贡献，$y$方向上的贡献，然后相加记录最小值；
计算贡献时可用前缀和维护减小复杂度；
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
| #include <bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
#define mod 998244353
#define MAXN 1e18
#define MS 100009
LL n,m;
LL px[MS],py[MS];
LL gx[MS],gy[MS];
LL qzx[MS],qzy[MS];
int main() {
ios::sync_with_stdio(false);
cin >> n;
for(int i=1;i<=n;i++){
LL x,y;
cin >> x >> y;
px[i] = gx[i] = x+y;
py[i] = gy[i] = x-y;
}
sort(gx+1,gx+n+1);
for(int i=1;i<=n;i++){
qzx[i] = qzx[i-1] + gx[i];
}
sort(gy+1,gy+n+1);
for(int i=1;i<=n;i++){
qzy[i] = qzy[i-1] + gy[i];
}
LL ans = MAXN;
for(int i=1;i<=n;i++){
LL xpos = lower_bound(gx+1,gx+n+1,px[i]) - gx;
LL ypos = lower_bound(gy+1,gy+n+1,py[i]) - gy;
LL xval = px[i]*xpos-qzx[xpos] + qzx[n]-qzx[xpos]-(n-xpos)*px[i];
LL yval = py[i]*ypos-qzy[ypos] + qzy[n]-qzy[ypos]-(n-ypos)*py[i];
ans = min(ans,xval+yval);
}
cout << ans/2 << "\n";
return 0;
}
|
