Luogu3964
Description
草原上住着一群小松鼠，每个小松鼠都有一个家。时间长了，大家觉得应该聚一聚。但是草原非常大，松鼠们都很头疼应该在谁家聚会才最合理。
每个小松鼠的家可以用一个点$(x,y)$表示,两个点的距离定义为点 $(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。输出一个整数，表示松鼠为了聚会走的路程和最小是多少。
Solution
观察题目发现，松鼠家之间的距离为切比雪夫距离，可以通过转换成曼哈顿距离求解，即问题转换为给出平面中的N个点，求一个点到其他所有点的曼哈顿距离之和最小是多少。
如果选定的点为第j个
答案即为$\sum_{i=1}^{N}dis(i,j)$,dis表示两个点的曼哈顿距离
将两个坐标拆开计算，可以得到
$ans_x = \sum_{i=1}^Ndis(j,i)$
$dis(1,j)+dis(2,j)+dis(3,j) +…+dis(n,j)$
将横坐标按照升序排序
$(x_j-x_1)+(x_j-x_2)+(x_j-x_3)+…+(x_j-x_{j-1})+(x_{j+1}-x_j)+…+(x_n-x_j)$
$\sum_{i=1}^{j-1}(x_j-x_i)+\sum_{i=j+1}^{N}(x_i-x_j)$
$(j-1)*x_j-\sum_{i=1}^{j-1}x_i + \sum_{i=j+1}^Nx_i-(N-j)*x_j$
$\sum_{i=1}^Nx_i-2\sum_{i=1}^jx_i-x_j*(n-2*j)$
于是可以使用前缀和优化，坐标排序后预处理前缀和
在每次进行计算时在有序坐标数组中找到对应的下标
精度问题可以先把坐标都扩大二倍，最后令答案处以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
55
|
#include<iostream>
#include<cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define debug cout<<0<<endl
#define ll long long
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
using namespace std;
int N;
struct point {
ll x, y;
} a[MAXN];
ll x[MAXN];
ll prex[MAXN];
ll y[MAXN];
ll prey[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
int xx, yy;
cin >> xx >> yy;
x[i] = a[i].x = (xx + yy);
y[i] = a[i].y = (xx - yy);
}
sort(x+1, x+N+1);
sort(y+1, y+N+1);
for (int i = 1; i <= N; i++) {
prex[i] = prex[i-1] + x[i];
prey[i] = prey[i-1] + y[i];
}
ll ans = __LONG_LONG_MAX__;
for (int i = 1; i <= N; i++) {
ll temp;
int lx = lower_bound(x+1,x+N+1,a[i].x) - x;
int ly = lower_bound(y+1,y+1+N,a[i].y) - y;
temp = (prex[N]-2*prex[lx]-a[i].x*(N-2*lx))
+(prey[N]-2*prey[ly]-a[i].y*(N-2*ly));
// cout << " list = "<< a[i].x << ' ' << a[i].y << ' ' << temp << endl;
ans = min(ans, temp);
}
cout << (ans/2);
return 0;
}
|
Zhiwei Zhang
included in Algorithm