UmiQS' Blog
0%

【AcWing 250】磁力块（分块 +BFS）

发表于 更新于 分类于 ， Valine：

1. 题目分析

AcWing 250 磁力块 题目描述

给定一个人的坐标 $ (x_0,y_0)$ （固定）和在这个位置上的初始磁石，以及其他 $ n$ 个剩余磁石的位置。每个磁石的信息有：位置坐标 $ (x,y) $ ，质量 $ m $ 、磁力 $ p $ 、磁力的作用半径 $ r $ 。一个磁石 $ M $ 能被这个人手上的某个磁石 $ M_0 $ 吸过来，当且仅当 $ M $ 的质量小于 $ M_0 $ 的磁力，且 $ M $ 与人的距离不大于 $ M_0$ 磁力的作用距离。磁石被吸引过来之后，可以被人自由使用，用来吸引其他可能被吸引的磁石。求所有能被人得到的磁石个数。

1.1. BFS 框架

求所有可能的结果，不难得出题目算法的总体框架是使用搜索实现，进一步地，应该使用 BFS 来实现。

1
2
3
4
5
6
7
8
9
ans = 0;
初始磁石进入队列q;
WHILE (q不为空)
    从q中弹出队首磁石x;
    FOR 磁石y IN 还未被吸引的磁石集合
        IF x.p >= y.m AND x.r >= y.dist THEN
            // y的质量不大于x的磁力，且在x的作用半径内
            将y加入队列q;
            ans++;

1.2. 分块优化

在 BFS 中，最耗时的是寻找还未被吸引并且满足被吸引条件的磁石。本题中，磁石被吸引的条件有两个：

  • 被吸引磁石质量 $\leq$ 使用的磁石的磁力
  • 被吸引磁石与人的距离 $\leq$ 使用的磁石的作用半径

所以需要使用数据结构维护磁石们的质量和距离序列，方便快速找到满足被队首磁石吸引条件的其他磁石。使用平衡树等数据结构比较复杂，这个时候分块就是一个比较好的选择。

把 $n$ 块磁石按照质量排序，并将序列分成 $T=\sqrt{n}$ 块。在每一块内部，再按照距离排序。这样对于每个队首的磁石 $x$ ，在序列中一定存在一个块号 $k$ ，满足：

  • 块号在 $[1, k)$ 范围内的，所有磁石的质量都不大于 $x$ 的磁力 $p_x$
  • 块号大于 $k$ 的，每个块内磁石的质量都大于 $p_x$
  • 第 $k$ 块内，有一部分磁石的质量不大于 $p_x$

只需记录每一个块内最重磁石的质量 $maxM$ ，然后在包含 $ T$ 个 $ maxM$ 的序列中二分查找最后一个大于 $p_x$ 的 $maxM$ 所在的块号 $k$ 。然后按照上述分类，分开处理。

  • 块号属于 $[1, k)$ 范围的，磁石的质量都已经满足条件。由于事先在块内已经按照距离升序排列，所以，不大于 $x$ 的作用范围 $ r_x$ 的只有各个块内的开头的连续一部分。只需要在每一块内从左边界开始暴力挨个扫描将还未被吸引去且距离满足条件的磁石入队即可。这就相当于每个块内左边连续的那一部分在经过 $ x$ 吸引后，对接下来的队列中的磁石再无关系。所以每个块内扫描到第一个大于 $r_x$ ，就可以跳出本块的循环，并将左边界设置为当前位置，这样被吸引的此时在下次就不会重复处理。二分查找的时间复杂度为 $O(\log \sqrt{n})=O(\frac{1}{2}\log n)=O(\log n)$ 。 $k$ 的上界不超过 $\sqrt{n}$ 。由于每个磁石只访问 1 次，所以扫描磁石的均摊复杂度为 $O(1)$ 。总共时间复杂度为 $O(\log n +1\cdot \sqrt{n})=O(\sqrt{n})$
  • 块号大于 $k$ 的，磁石的质量已经不符合要求，不做处理。
  • 第 $k$ 块内，有一部分的质量不大于 $p_x$ ，另一部分大于 $p_x$ ，并且出现的位置可能不连续。所以，必须对第 $k$ 块内部的元素从它当前的左边界挨个扫描至右边界，把所有质量和距离同时满足条件的磁石入队。注意，这里不修改左边界。时间复杂度为 $O(\sqrt{n})$ 。

所以，处理 $x$ 的时间复杂度为 $O(\sqrt{n}+\sqrt{n}) = O(\sqrt{n})$ 。BFS 总的时间复杂度为 $O(n\sqrt{n})$ 。

2. 代码实现

为了避免开方运算，距离和半径统一做平方运算。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
typedef long long LL;
const int MAXN = 250005;
int n, t, ans, v[MAXN] = {0};
int L[MAXN] = {0}, R[MAXN] = {0}, MaxM[MAXN] = {0};
LL xx0, yy0; // 初始坐标

struct node {
    LL d, m, p, r;
    node() {d = m = p = r = 0;}
} L0, a[MAXN];

queue<node> q;

inline LL GetDist(LL x, LL y) {return (x-xx0)*(x-xx0) + (y-yy0)*(y-yy0);}

inline bool cmp_m(const node &A, const node &B) {return A.m < B.m;} // 按质量

inline bool cmp_d(const node &A, const node &B) {return A.d < B.d;} // 按离(xx0, yy0)的距离

void init()
{
    LL x, y;
    scanf("%lld%lld%lld%lld%d", &xx0, &yy0, &L0.p, &L0.r, &n);
    L0.r *= L0.r;
    for(int i=1; i<=n; i++)
    {
        scanf("%lld%lld%lld%lld%lld", &x, &y, &a[i].m, &a[i].p, &a[i].r);
        a[i].r *= a[i].r; // 用平方表示距离
        a[i].d = GetDist(x, y);
    }
    sort(a+1, a+n+1, cmp_m);
    int len = sqrt(n);
    t = sqrt(n);
    for(int i=1; i<=t; i++)
    {
        L[i] = (i-1) * len + 1;
        R[i] = i * len;
        // MaxM[i]记录第i块最重的那个，由于a已经按重量排序，所以一定是块内最右边的那个
        MaxM[i] = a[R[i]].m;
        sort(a+L[i], a+R[i]+1, cmp_d); // 块内部按照距离排序，此时质量不再有序
    }
    if(R[t] < n)
    {
        t++; L[t] = R[t-1] + 1; R[t] = n;
        MaxM[t] = a[R[t]].m;
        sort(a+L[t], a+R[t]+1, cmp_d);
    }
}

void BFS()
{
    ans = 0;
    q.push(L0); // L0的m和d已设置为0
    while(!q.empty())
    {
        node f = q.front(); q.pop();
        int k = upper_bound(MaxM+1, MaxM+t+1, f.p) - (MaxM+1);
        k = (MaxM[k] <= f.p) ? k : (k-1); // 评测数据未体现这一点，但是理论上应该有这一句
        for(int i=1; i<=k; i++)
        {
            int j = L[i];
            while(j<=R[i] && a[j].d <= f.r)
            {
                if(!v[j])
                {
                    v[j] = 1;
                    q.push(a[j]);
                    ans++;
                }
                j++;
            }
            L[i] = j; // 更新块的左边界（现在块内的L左边一段已经被拿走了）
        }
        if(k+1 <= t)
        {
            k++;
            for(int i=L[k]; i<=R[k]; i++)
              if(!v[i] && a[i].m<=f.p && a[i].d<=f.r)
              {
                  v[i] = 1;
                  q.push(a[i]);
                  ans++;
                  // 这里不用修改最后一块的左端点
                  // 因为质量不再递增排列，可能是跳着取的
              }
        }
    }
    printf("%d\n", ans);
}

int main()
{
    init();
    BFS();
    return 0;
}