Codeforces Round #762 (Div. 3) G. Unusual Minesweeper

题目

  • 原题地址:G. Unusual Minesweeper
  • 题目编号:1619G
  • 目标算法:贪心、并查集
  • 难度评分:2000

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
上一篇:补丁星期二活动即将到来 Windows 10多个版本将迎更新


下一篇:牛客练习赛91 C.魔法学院(hard version) (dsu区间染色)