文章

25

粉丝

0

获赞

0

访问

68517

头像
分块(磁力块)
经验总结
发布于2020年4月21日 17:44
阅读数 2643

分块+bfs: 

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = (int)2e6;
const int w = 500;//块长度
typedef long long ll;
ll xx, yy, l[N], r[N], num, n, x, y, D[N], v[N];//D[N]记录每一块距离源点最大的d
struct node{
	ll m, r, d, p;
}a[N];
bool cmp_d(node a, node b){
	return a.d < b.d;
}
bool cmp_m(node a, node b){
	return a.m < b.m;
}
ll dfs(){
	queue<ll >q;
	q.push(0);
	ll ans = 1;
	while (q.size()){
		ll t = q.front();
		q.pop();
		for (int i = 1; i <= num; i++){//对于每一个块进行更新
			if (D[i]>a[t].r){//两边暴力
				for (ll j = l[i]; j <= r[i]; j++){
					if (!v[j] && a[j].d <= a[t].r&&a[j].m <= a[t].p){
						q.push(j);
						ans++;
						v[j] = 1;
					}
				}
				break;//已经是最右边的块了,直接break
			}
			while (l[i] <= r[i] && a[l[i]].m <= a[t].p){//距离已经在磁力半径之内,判断质量
				if (!v[l[i]]){
					q.push(l[i]);
					ans++;
				}
				l[i]++;
			}
		}
	}
	return ans;
}
int main(){
	cin >> xx >> yy >> a[0].p >> a[0].r >> n;
	a[0].r *= a[0].r;
	for (int i = 1; i <= n; i++){
		cin >> x >> y >> a[i].m >> a[i].p >> a[i].r;
		a[i].r *= a[i].r;
		a[i].d = (x - xx)*(x - xx) + (y - yy)*(y - yy);
	}
	//按距离d进行排序
	sort(a+1, a + n+1, cmp_d);
	//分组
	for (ll i = 1; i <= n; i+=w){
		l[++num] = i;
		r[num] = min(n, i + w - 1);
		D[num] = a[r[num]].d;
		sort(a + l[num], a + r[num] + 1, cmp_m);//快内按照质量进行排序
	}
	ll ans=dfs();
	cout << ans-1 << endl;

	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发