CH #46A - 磁力块 - （分块）

比眉伴天荒 2021-12-16 04:40 176阅读 0赞

## 题面： ##

**描述**  
在一片广袤无垠的原野上，散落着N块磁石。每个磁石的性质可以用一个五元组(x,y,m,p,r)描述，其中x,y表示其坐标，m是磁石的质量，p是磁力，r是吸引半径。若磁石A与磁石B的距离不大于磁石A的吸引半径，并且磁石B的质量不大于磁石A的磁力，那么A可以吸引B。  
小取酒带着一块自己的磁石L来到了这篇原野的(x0,y0)处，我们可以视为磁石L的坐标为(x0,y0)。小取酒手持磁石L并保持原地不动，所有可以被L吸引的磁石将会被吸引过来。在每个时刻，他可以选择更换任意一块自己已经获得的磁石（当然也可以是自己最初携带的L磁石）在(x0,y0)处吸引更多的磁石。小取酒想知道，他最多能获得多少块磁石呢？

**输入格式**  
第一行五个整数x0,y0,pL,rL,N，表示小取酒所在的位置，磁石L磁力、吸引半径和原野上散落磁石的个数。  
接下来N行每行五个整数x,y,m,p,r，描述一块磁石的性质。

**输出格式**  
输出一个整数，表示最多可以获得的散落磁石个数（不包含最初携带的磁石L）。

**样例输入**  
0 0 5 10 5  
5 4 7 11 5  
\-7 1 4 7 8  
0 2 13 5 6  
2 -3 9 3 4  
13 5 1 9 9  
**样例输出**  
3  
**数据范围与约定**  
对于30%的数据，1<=N<=1000。  
对于100%的数据，1<=N<=250000，-10^9<=x,y<=10^9，1<=m,p,r<=10^9。

## 分析： ##

## 首先，假设手上有若干块磁铁，我要让我吸到的磁铁尽可能多，显然最简单的办法就是把手上的磁铁都拿来吸吸看，把能吸到的都吸过来，所以可以用类似于BFS的形式，对手头的磁铁用一个队列维护，取出队头磁铁尝试吸引，把能吸到的磁铁都入队，反复如此知道队列为空，即可知道已经吸到了所有能被吸过来的磁铁。 ##

## 由于考虑一个磁铁能不能被吸引过来，要看满足两个条件与否： ##

## 　　1、距离 ≤ 吸引半径 ##

## 　　2、手头磁铁的磁力 ≥ 被吸引的磁铁的质量 ##

## 对平面上所有磁铁按照与我的距离从近到远进行升序排序，分成 T ##

## 块，显然每个分块内含有 O(NT) ##

## 个磁铁，再对每个分块内的磁铁按照质量升序排序， ##

## 那么，对于当前的查询 Q(p,r)，对于吸引半径 r，必然存在一个整数 k，满足： ##

## 　　1、第 1∼k个分块中所有磁铁距离均小于等于 r； ##

## 　　2、第 k+2个分块中所有磁铁距离均大于 r，不可能被吸引； ##

## 分类讨论： ##

## 　　①对于满足距离条件的第 1∼k个分块，分别从每个块的块头开始遍历，直到某一个磁铁质量大于磁力 p时就停止，同时将该磁铁设为新的块头； ##

## 　　②对于不确定是否满足距离条件的第 k+1个分块，暴力枚举块内所有磁铁，判断是否能被吸引，能吸引的就取走即可。 ##

## 时间复杂度： ##

## 　　对于①，对于某一个分块，由于其中每个磁铁都只会被取走一次，均摊复杂度为 O(1) ##

## ，一次询问最多处理 O(T) 个分块，因此每次询问时间复杂度 O(T)； ##

## 　　对于②，每次询问需要 O(NT)的暴力枚举。 ##

## 　　①和②合起来就是 O(T+NT)，显然取 T=√ N时最小，为 O(√N)；又最多有 O(N) 次询问，总时间复杂度 O(N√N)。 ##

## 参考：[https://www.cnblogs.com/dilthey/p/9789584.html。][https_www.cnblogs.com_dilthey_p_9789584.html] ##

## 代码： ##

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N = 250006;
    struct P {
    	int x, y, m, p, r;
    } p[N], q[N];
    bool b[N];
    int n, L[N], R[N], M[N];
    
    bool cmp(P a, P b) {
    	return a.m < b.m;
    }
    
    bool cmp0(P a, P b) {
    	return (ll)(a.x - q[0].x) * (a.x - q[0].x) + (ll)(a.y - q[0].y) * (a.y - q[0].y) < (ll)(b.x - q[0].x) * (b.x - q[0].x) + (ll)(b.y - q[0].y) * (b.y - q[0].y);
    }
    
    bool pd(P a, P b) {
    	return (ll)(q[0].x - b.x) * (q[0].x - b.x) + (ll)(q[0].y - b.y) * (q[0].y - b.y) <= (ll)a.r * a.r;
    }
    
    int main() {
    	cin >> q[0].x >> q[0].y >> q[0].p >> q[0].r >> n;
    	for (int i = 1; i <= n; i++)
    		scanf("%d %d %d %d %d", &p[i].x, &p[i].y, &p[i].m, &p[i].p, &p[i].r);
    	sort(p + 1, p + n + 1, cmp);/// 按质量排序
    	int t = sqrt(n); /// 块的大小
    	/// 预处理每一块的左右端点和最大质量
    	for (int i = 1; i <= t; i++) {
    		L[i] = (i - 1) * t + 1;
    		R[i] = i * t;
    		M[i] = p[R[i]].m;
    		sort(p + L[i], p + R[i] + 1, cmp0);/// 内部按距离排序
    	}
    	/// 末尾
    	if (R[t] < n) {
    		L[t+1] = R[t] + 1;
    		R[++t] = n;
    		M[t] = p[R[t]].m;
    		sort(p + L[t], p + R[t] + 1, cmp0);
    	}
    	/// BFS框架
    	int l = 0, r = 1;
    	memset(b, 0, sizeof(b)); /// 搜索队列
    	while (l < r) {
    		int k = 0;
    		for (int i = 1; i <= t; i++)
    			if (M[i] <= q[l].p) k = i;
    			else break;
            /// 第 1-k 个分块中所有磁铁距离均小于等于 r
    		for (int i = 1; i <= k; i++)
    			while (L[i] <= R[i] && pd(q[l], p[L[i]])) {
    				if (!b[L[i]]) {
    					b[L[i]] = 1;
    					q[r++] = p[L[i]];
    				}
    				++L[i];
    			}
            /// 分别从每个块的块头开始遍历，直到某一个磁铁质量大于磁力 p 时就停止，同时将该磁铁设为新的块头
    		if (t != k++)
    			for (int i = L[k]; i <= R[k]; i++)
    				if (!b[i] && p[i].m <= q[l].p && pd(q[l], p[i])) {
    					b[i] = 1;
    					q[r++] = p[i];
    				}
            /// 尾巴（残余块处理）
    		++l;
    	}
    	cout << r - 1 << endl;
    	return 0;
    }

[https_www.cnblogs.com_dilthey_p_9789584.html]: https://www.cnblogs.com/dilthey/p/9789584.html