题目链接
显然,题目要求我们求切比雪夫距离,不会的可以去看一下attack的博客。
考虑枚举所有的点
转换为曼哈顿距离后.
那么对于这个点的路程和是。
[sum_{i=1}^n | x_i - x_k| + |y_i - y_k|
]
考虑是绝对值.
将横纵坐标(sort)一下,(lower_bound)查询即可
接下来就简单多了
分情况讨论即可.
然后我只是化简了一下式子.
需要注意的是.由于转化为曼哈顿距离除以二时会有精度问题,所以这里先不除以二,最后的答案才除以二.
#include <iostream>
#include <algorithm>
#include <cstdio>
#define ll long long
const int maxN = 100000 + 7;
using namespace std;
ll x[maxN],y[maxN],n;
ll std_x[maxN],std_y[maxN];
ll sum_x[maxN],sum_y[maxN];
void Sub2() {
ll ans = 1e18;
for(int i = 1;i <= n;++ i) {
x[i] = std_x[i];
y[i] = std_y[i];
}
sort(x + 1,x + n + 1);
sort(y + 1,y + n + 1);
for(int i = 1;i <= n;++ i) sum_x[i] = sum_x[i - 1] + x[i];
for(int i = 1;i <= n;++ i) sum_y[i] = sum_y[i - 1] + y[i];
for(int i = 1;i <= n;++ i) {
ll sum = 0;
ll pos_x = lower_bound(x + 1,x + n + 1,std_x[i]) - x;
ll pos_y = lower_bound(y + 1,y + n + 1,std_y[i]) - y;
sum = (2 * pos_x - n) * x[pos_x] - 2 * sum_x[pos_x] + sum_x[n] +
(2 * pos_y - n) * y[pos_y] - 2 * sum_y[pos_y] + sum_y[n];
ans = min(ans,sum);
}
printf("%lld", ans / 2);
return ;
}
int main() {
scanf("%lld",&n);
ll g,z;
for(int i = 1;i <= n;++ i) {
scanf("%lld%lld",&g,&z);
std_x[i] = g + z;
std_y[i] = g - z;
}
Sub2();
return 0;
}