链接
https://ac.nowcoder.com/acm/problem/51114
题意
有 $N$ 块磁石，每个磁石的性质可以用一个五元组 $(x,y,m,p,r)$ 描述，其中 $x,y$ 表示其坐标，$m$是磁石的质量，$p$ 是磁力，$r$ 是吸引半径
若磁石 A 与磁石 B 的距离不大于磁石A的吸引半径，并且磁石 B 的质量不大于磁石 A 的磁力，那么 A 可以吸引 B
现在有一块磁石 L，坐标为 $(x0,y0)$，保持原地不动，所有可以被 L 吸引的磁石将会被吸引过来。
在每个时刻，可以选择更换任意一块自己已经获得的磁石（当然也可以是自己最初携带的L磁石）在 $(x0,y0)$ 处吸引更多的磁石
最多能获得多少块磁石？
思路
分块
利用 BFS，建立队列，先将磁石 L 放入队列
将 $n$ 块磁石按照质量从小到大排序并分成 $\sqrt{n}$ 段，再将每一段中磁石按离 $(x0,y0)$ 的距离从小到大排序
每次队头磁石吸引磁石时，必能找到第 $k$ 段使：
$1 \sim k-1$ 段中的每一块磁石的质量都小于等于队头的磁力
$k+1$ 段后的磁石的质量都大于队头的磁力
因此对于 $1 \sim k-1$ 段的磁石，如果该块磁石未被吸引并且距离小于等于队头的磁力，入队，当扫描到第一个距离大于队头的磁力时，将该段的段首改为该点，这样已经被吸引的磁石就不会被扫描到
对于第 $k$ 段的磁石，朴素扫描即可
时间复杂度为 $O(n\sqrt{n})$
代码
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n,t;
ll x_0,y_0;
int cnt;
int L[500],R[500],M[500];
bool st[N];
int ans;
struct node {
int m,p;
ll d,r;
}s[N];
bool cmp1(node a,node b) {
return a.m<b.m;
}
bool cmp2(node a,node b) {
return a.d<b.d;
}
void pre() {
cin>>x_0>>y_0>>s[0].p>>s[0].r>>n;
s[0].r*=s[0].r;
for(int i=1;i<=n;i++) {
ll x,y,r;
int m,p;
cin>>x>>y>>m>>p>>r;
s[++cnt]={m,p,(x-x_0)*(x-x_0)+(y-y_0)*(y-y_0),r*r};
}
sort(s+1,s+1+n,cmp1);
t=sqrt(n);
for(int i=1;i<=t;i++) {
L[i]=R[i-1]+1;
R[i]=i*t;
}
if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
for(int i=1;i<=t;i++) {
M[i]=s[R[i]].m;
sort(s+L[i],s+1+R[i],cmp2);
}
}
void bfs() {
queue<int>q;
q.push(0);
while(!q.empty()) {
int now=q.front();
q.pop();
for(int i=1;i<=t;i++) {
if(M[i]>s[now].p) {
for(int j=L[i];j<=R[i];j++) {
if(!st[j]&&s[j].m<=s[now].p&&s[j].d<=s[now].r) {
st[j]=true;
ans++;
q.push(j);
}
else if(s[j].d>s[now].r) break;
}
break;
}
while(L[i]<=R[i]&&s[L[i]].d<=s[now].r) {
if(!st[L[i]]) {
st[L[i]]=true;
ans++;
q.push(L[i]);
}
L[i]++;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
pre();
bfs();
cout<<ans<<endl;
return 0;
}
|