题目
1.题目大意
- 有 n 个雷,每个雷都有自己的坐标 (x, y) 以及爆炸时间
- 所有雷都会按照 “+” 的形状爆炸,四个方向的波及范围均为 k
- 一个雷爆炸后如果其爆炸范围内有其他雷,则被波及的雷也会在同一时刻爆炸
- 要求:每秒选定一个雷引爆,使所有的雷爆炸的总时间最短
2.题目分析
- 思路:将所有可以互相引爆的雷算作一个雷(用并查集来维护),这一雷组的爆炸时间就是其中所有雷中最短的爆炸时间,然后每秒从时间最长的雷组开始引爆,最后的答案就是自爆的雷与手动引爆雷的交汇点。
3.题目代码
#include <bits/stdc++.h>
#define fr first
#define sc second
#define ll long long
using namespace std;
const ll inf = 1e18;
ll a[200069], dsu[200069], ex[200069];
pair<pair<ll, ll>, ll> as[200069];//存储每颗雷的信息
ll fd(ll x)//并查集
{
if (dsu[x]!=x)
dsu[x] = fd(dsu[x]);
return dsu[x];
}
int main()
{
ll t;
cin >> t;
while(t--)
{
ll n, d;
ll x, y;
cin >> n >> d;
for(int i=1;i<=n;i++)
{
cin >> x >> y >> a[i];
as[i] = {{x, y}, i};
dsu[i] = i;
}
for(int j=0;j<2;j++)//两次,一次跑x一次跑y
{
sort(as + 1, as + n + 1);
for (int i=2;i<=n;i++)
{
ll y1 = as[i].fr.fr;
ll y2 = as[i-1].fr.fr;
ll x1 = as[i].fr.sc;
ll x2 = as[i-1].fr.sc;
if (y1==y2&&x1-x2<=d)
{
ll l = as[i-1].sc;
ll p = as[i].sc;
a[fd(p)] = min(a[fd(p)], a[fd(l)]);//爆炸时间为较小的那个
dsu[fd(l)] = fd(p);//合并成一个集合p
}
}
for (int i=1;i<=n;i++)
swap(as[i].fr.fr, as[i].fr.sc);
}
ll j = 0;
for(int i=1;i<=n;i++)
if (fd(i) == i)
ex[j++] = a[i];
sort(ex, ex+j, greater<long long>());
ex[j] = -inf;
for (int i=0;i<j;i++)
{
//cout << i << " " << ex[i] << " " << ex[i+1] << endl;
if (ex[i+1]<i+1)
{
cout << i << endl;
break;
}
else if(ex[i+1]==i+1)
{
cout << i+1 << endl;
break;
}
}
}
}
//1
//5 0
//0 1 1
//-1 -1 6
//-1 0 8
//1 -1 3
//0 0 3