题意简述
给定 \(n\) 个地雷的坐标及其自动引爆的时间。每个地雷引爆时都会使它的横纵坐标距离的 \(k\) 的形状为"+"的范围内 \((x\pm k,y\pm k)\) 的地雷引爆。同时，自 \(0\) 秒开始的每秒都可以任意引爆一颗地雷，求所有地雷都引爆的最小时间（即求最后一个地雷引爆的时间）。
思路分析
按照贪心的思想，引爆较晚爆炸的地雷会使最后一个地雷引爆的时间提前，对答案有贡献。但是后引爆的地雷可能会被先引爆的地雷引爆，所以不能按时间从后往前引爆。那该用什么方法处理？
同时引爆的几个地雷可以看做一个地雷引爆，那怎么把多个地雷合并成一个地雷呢？
并查集！
于是我们需要将互相能够引爆的几个地雷整到一个集合中，两两判断是否在一个集合然后合并即可，和 P3958 [NOIP2017 提高组] 奶酪 思路大致相同。
\(1\le n\le2\times10^5\)
\(O(n^2)\) 合并显然过不去，合并反而成了个问题。
于是我们发现，当我们以单个坐标为第一关键字，另一个坐标为第二个关键字将这些地雷排序后，只需判断相邻的两个地雷是否能够合并即可。若相邻的两个地雷在此方向不能合并，则与它不相邻的下一个地雷一定也无法合并，因为距离是越来越远的，只有此方向的距离在 \(k\) 之内的地雷才能合并。
于是就有了两个方向的合并，\(O(n\log n)\) 排序，\(O(n)\) 合并。
struct coordinate//地雷
{int x,y,t,id;//坐标，引爆时间，地雷编号
}c[N];sort(c+1,c+n+1,cmp_x);//以x为第一关键字，y为第二关键字排序
for(int i=1;i<n;i++)if(c[i].x==c[i+1].x&&c[i+1].y-c[i].y<=k)//y方向能够引爆 merge(c[i].id,c[i+1].id);
sort(c+1,c+n+1,cmp_y);//以y为第一关键字，x为第二关键字排序
for(int i=1;i<n;i++)if(c[i].y==c[i+1].y&&c[i+1].x-c[i].x<=k)//x方向能够引爆 merge(c[i].id,c[i+1].id);
在合并地雷之后按照新的地雷引爆时间从大到小开始引爆，直到全部引爆为止时间最小。
完整代码
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int T,n,k,cnt;//cnt是新的地雷数组的计数器
int fa[N],newc[N];//并查集数组，合并后的新地雷数组，此时地雷互不影响，坐标已没有任何用处，只需一个数组存引爆时间
map<int,int>vis;//vis的map数组存此集合内的所有地雷在新的地雷数组中的临时编号，若vis值为0则此集合还未加入新的地雷数组
struct coordinate//地雷
{int x,y,t,id;//坐标，引爆时间，地雷编号
}c[N];
int re()//朴素的快读
{int x=0,p=1;char y=getchar();for(;y>'9'||y<'0';y=getchar())if(y=='-')p=-p;for(;y>='0'&&y<='9';y=getchar())x=x*10+y-'0';return x*p;
}
void wr(int x)//朴素的快写
{if(x<0)putchar('-'),x=-x;if(x>9)wr(x/10);putchar(x%10+'0');
}
int find(int x)//朴素的路径压缩并查集查找操作
{if(fa[x]==x)return x;return fa[x]=find(fa[x]);//路径压缩
}
void merge(int x,int y)//朴素的合并操作
{int f1=find(x),f2=find(y);if(f1==f2)return;fa[f1]=f2;
}
bool cmp_x(const coordinate &a,const coordinate &b)
{return (a.x<b.x)||(a.x==b.x&&a.y<b.y);
}
bool cmp_y(const coordinate &a,const coordinate &b)
{return (a.y<b.y)||(a.y==b.y&&a.x<b.x);
}
signed main()
{T=re();while(T--){n=re(),k=re();cnt=0,vis.clear();//初始化 for(int i=1;i<=n;i++)fa[i]=i,newc[i]=0x7fffffff;//由于newc存的是最早引爆时间，初始值设为最大值 for(int i=1;i<=n;i++)c[i].x=re(),c[i].y=re(),c[i].t=re(),c[i].id=i;sort(c+1,c+n+1,cmp_x);//以x为第一关键字，y为第二关键字排序 for(int i=1;i<n;i++)if(c[i].x==c[i+1].x&&c[i+1].y-c[i].y<=k)//y方向能够引爆 merge(c[i].id,c[i+1].id);sort(c+1,c+n+1,cmp_y);//以y为第一关键字，x为第二关键字排序 for(int i=1;i<n;i++)if(c[i].y==c[i+1].y&&c[i+1].x-c[i].x<=k)//x方向能够引爆 merge(c[i].id,c[i+1].id);for(int i=1;i<=n;i++){int f=find(c[i].id);//所在集合编号 if(!vis[f])//此集合没在新地雷数组中出现过 cnt++,vis[f]=cnt;//将此集合所在新地雷数组的编号记录下来 newc[vis[f]]=min(newc[vis[f]],c[i].t);//更新最早引爆时间 }sort(newc+1,newc+cnt+1);//引爆时间排序 for(int i=0;i<=cnt;i++)//0时刻开始 if(newc[cnt-(i+1)]<=i)//不被手动引爆的最晚引爆的时间比当前时间小 {wr(i),putchar('\n');break;}}return 0;
}