题目链接

解题思路

这道题目中，我们为了更快的排除一些不可选的磁力块，可以选择分块。总体以m从大到小排序，块内以dis排序（颠倒过来应该也可以）。即以两个对于吸引的决定项排序。

我们设k是大小交替的一块（即需要考虑的，但并不是全部都满足m<now.p)。先记录下每一块的最大最小值，O(sqrt(n))查找。如果now.p<maxn[k]，则表示这一块是k。（当然可能没有大小交替的块，k查找到的则是第一个全部大于now.p的，我们可以和k一样考虑，不影响答案。）

对于k前面的，由于所有m都符合，只需要考虑dis，如果dis[i]>now.r，则说明这块中它和它之后的都不可取了，直接跳到下一块。当然我们需要设fi和la作为块的头和尾，每次取一个数都要fi[i]++;

对于k，我们不可以直接fi[i]++。因为有一种情况“大小大”，我们取的是小的，但是大的却被排除了，明显不对。所以我们维护一个vis数组对于这种奇坑无比的情况进行特判。

代码

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
long long xx,yy,pl,rl;
int num,n;
struct stone{
    long long x,y,m,p,r,dis;
}s[250005];
bool vis[250005];
//m<=p,dis<=r;

int fi[5005],la[5005];
int maxn[5005],minn[5005];
bool cmp(stone aa,stone bb){
    return aa.m<bb.m;
}
bool cmpp(stone aa,stone bb){
    return aa.dis<bb.dis;
}
int sq;
void rd(){
    scanf("%lld%lld%lld%lld%d",&xx,&yy,&pl,&rl,&n);
    for(int i=1;i<=n;i++){
        vis[i]=false;
        scanf("%lld%lld%lld%lld%lld",&s[i].x,&s[i].y,&s[i].m,&s[i].p,&s[i].r);
        s[i].r=s[i].r*s[i].r;
        s[i].dis=(xx-s[i].x)*(xx-s[i].x)+(yy-s[i].y)*(yy-s[i].y);
    }
}
void init(){
    sort(s+1,s+1+n,cmp);
    sq=sqrt(n);
    num=sq;
    for(int i=1;i<=num;i++){
        fi[i]=(i-1)*sq+1,la[i]=min(n,i*sq);
    }
    if(sq*sq<n){
        num++;
        fi[num]=sq*sq+1;
        la[num]=n;
    }
    for(int i=1;i<=num;i++){
        maxn[i]=s[la[i]].m,minn[i]=s[fi[i]].m;
        sort(s+fi[i],s+la[i]+1,cmpp);
    } 
    
}
queue<stone> q;
int main(){
    rd();
    init();
    int gett=0;
    stone tmp;
    tmp.dis=0,tmp.m=0,tmp.p=pl,tmp.r=rl*rl,tmp.x=xx,tmp.y=yy;
    q.push(tmp);
    stone now;
    while(gett!=n&&!q.empty()){
        now=q.front();
        q.pop();
        int k=1;
        while(k<=num&&now.p>=maxn[k])k++;//第一块 
        for(int i=1;i<k;i++){
            for(int j=fi[i];j<=la[i];j++){
                if(s[j].dis>now.r)break;//由于在一块之内是按照dis排序的，所以当前dis>r，则所有之后的dis都大于r
                if(vis[j])fi[i]++;
                if(s[j].m<=now.p&&!vis[j]){
                    gett++;
                    q.push(s[j]);
                    fi[i]++;
                    vis[j]=true;
                }    
            }
        }
        if(k<=num&&now.p>=minn[k]){
            for(int j=fi[k];j<=la[k];j++){
                if(s[j].dis>now.r)break;
                if(s[j].m<=now.p&&!vis[j]){
                    gett++;
                    q.push(s[j]);
                    vis[j]=true;
                }
            }
        }
    }
    printf("%d\n",gett);
    return 0;
}

本文链接：http://kaispace.com.cn/index.php/archives/715/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者