蓝桥杯2022年第十三届省赛真题-扫雷（c语言）排序+二分

一.暴力解法

思路：用队列去存储排雷火箭，依次查找每个排雷火箭能引爆在范围内的雷，并将雷入队（将在范围内的雷看做成排雷火箭继续引爆）

代码如下：

#includestruct node
{
    int x,y,d;
} a[100000],p[100010];
int vis[100000],t,n;
long long juli(int x,int y,int xx,int yy)
{
    return (long long)((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
int main()
{
    int i,j,m;
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].d);
    for(i=1; i<=m; i++)
        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].d);

    int l=0,r=m+1;
    while(++l<r)
    {
        for(i=1; i<=n; i++)
        {
            //用vis来记录是否已经入队
            if(vis[i]==0&&juli(p[l].x,p[l].y,a[i].x,a[i].y)<=(long long )p[l].d*p[l].d)//要是在范围内就加入队列变成排雷火箭
            {
                vis[i]=1;
                t++;
                p[r++]=a[i];
            }
        }
    }
    printf("%d",t);
    return 0;
}

二.排序+二分查找

由于数据范围较大一定会出现时间超限，所以得想如何去优化哪一步

每次查找范围内的没有引爆的雷，这步查找可以进行优化

思路：将所有雷都按照雷的x坐标进行排序，然后每次查找都采用二分查找，由于雷一定会在（x-r，x+r）的范围内，所以采用二分查找出两个边界，循环该范围内的雷即可

注意事项：二分查找由于数据可能相等，导致漏掉几个，而出错（解决方法见代码）

代码如下：

#includestruct node
{
    int x,y,d;
} a[100000],p[100010];
int vis[100000],t,n;
int kuai(int xx,int yy)//给炸雷的x排序
{
    int i=xx,j=yy;
    struct node t=a[(i+j)/2];
    do
    {
        while(a[i].xt.x) j--;
        if(i<=j)
        {
            struct node m=a[i];
            a[i]=a[j];
            a[j]=m;
            i++;
            j--;
        }
    }
    while(i<=j);
    if(xx<j) kuai(xx,j);
    if(i<yy) kuai(i,yy);
}

long long juli(int x,int y,int xx,int yy)
{
    return (long long)((x-xx)*(x-xx)+(y-yy)*(y-yy));
}

int fun(int sum)//查找在横坐标为你sum位置的点排在炸弹的第几位
{
    int r=n,l=1,mid;
    while(l<r)
    {
        mid=(r+l)/2;
        if(sum<=a[mid].x) r=mid;
        else l=mid+1;
    }
    return l;
}

int main()
{
    int i,j,m;
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].d);
    for(i=1; i<=m; i++)
        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].d);

    kuai(1,n);

    int l=0,r=m+1;
    while(++l<r)
    {
        int xx,yy;
        xx=p[l].x-p[l].d,yy=p[l].x+p[l].d;
        xx=fun(xx-1),yy=fun(yy+1);//可能会出现相等的数据，而只包含到其中的一个，所以扩展所查找的范围即可
        
        for(i=xx; i<=yy; i++)//搜寻在该范围内的炸雷
        {
            if(vis[i]==0&&juli(p[l].x,p[l].y,a[i].x,a[i].y)<=(long long )p[l].d*p[l].d)//要是在范围内就加入队列变成排雷火箭
            {
                vis[i]=1;
                t++;
                p[r++]=a[i];
            }
        }
    }
    printf("%d",t);
    return 0;
}