四平网站建设在线咨询,做海报的网站什么编辑器,自己做的网站能放到网上么,网站留言板作用还是一道好题的 对于一个磁石是否被吸引#xff0c;有两个关键字#xff1a;距离和质量。#xff08;二维偏序#xff1f;#xff1f;#xff09; 好像是很厉害的分块姿势#xff0c;先按第一关键字排序#xff0c;在块中按第二关键字排 进行bfs#xff0c;对于当前磁…还是一道好题的 对于一个磁石是否被吸引有两个关键字距离和质量。二维偏序 好像是很厉害的分块姿势先按第一关键字排序在块中按第二关键字排 进行bfs对于当前磁石有1~k-1个块是第一关键字全部小于等于当前磁石的那么暴力从块首往后找到第一个第二关键字大于当前磁石属性的那么前面都捡走以后可以从这里开始找。 暴力枚举第k个块找答案。 一个优化就是找k的时候直接比较当前块的最大值就行了因为当前的属性肯定是kminkmax滴 垃圾CH本机AC提交WA幸好最后我搞对了 #includecstdio
#includeiostream
#includecstring
#includecstdlib
#includealgorithm
#includecmath
using namespace std;
typedef long long LL;int n;
struct node{LL dis,m,p,r;}a[310000];bool v[310000];
bool cmp1(node n1,node n2){return n1.mn2.m;}
bool cmp2(node n1,node n2){return n1.disn2.dis;}int block,st[310000];
struct LIST
{LL p,r;
}list[310000];
int be[610];LL mx[610];int findk(LL p)
{for(int i1;iblock;i)if(pmx[i])return i;return block1;
}int main()
{freopen(1.in,r,stdin);freopen(1.out,w,stdout);LL xx,yy,x,y;scanf(%lld%lld%lld%lld%d,xx,yy,list[1].p,list[1].r,n);for(int i1;in;i){scanf(%lld%lld%lld%lld%lld,x,y,a[i].m,a[i].p,a[i].r);a[i].dis(x-xx)*(x-xx)(y-yy)*(y-yy);}sort(a1,an1,cmp1);block(int(sqrt(double(n1))))1;for(int i1;in;i)st[i](i-1)/block1;for(int i1;iblock;i){int St(i-1)*block1,Edmin(i*block,n);mx[i]a[Ed].m;if(StEd)sort(aSt,aEd1,cmp2);}for(int i1;iblock;i)be[i]1;memset(v,false,sizeof(v));int head1,tail2,ans0;while(headtail){LL plist[head].p,rlist[head].r;int kfindk(p);for(int i1;ik-1;i){for(int jbe[i];jblock(i-1)*blockjn;j){int u(i-1)*blockj;if(a[u].disr*r){be[i]j;break;}{if(v[u]false){v[u]true;ans;list[tail].pa[u].p, list[tail].ra[u].r;tail;}}}}if(k!block1){for(int jbe[k];jblock(k-1)*blockjn;j){int u(k-1)*blockj;if(a[u].disr*r)break;else if(a[u].mp){if(v[u]false){v[u]true;ans;list[tail].pa[u].p, list[tail].ra[u].r;tail;}}}}head;}printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/AKCqhzdy/p/9432686.html
