自己思考的时候思考错了,首先 un_map<pair<int, int>, int>
,只能用map
。然后只考虑了排雷引爆雷的情况,利用曼哈顿距离,看能被引爆多少个,但我没有考虑雷被引爆的时候会引爆周围的雷。
hhhh我以为图论的题我能做出来才选这题的
840. 模拟散列表
总思路:
将所有的雷按x 从小到大排序。若在同一个位置,就只保留最大的半径。遍历所有的雷,若能引爆别人,二者之间就建立有向边
。点数量多用邻接表
。因为是排序的,所以一有无解情况就break
掉。然后输入火箭,遍历所有火箭,同时计算能引爆的点,找到一个因火箭可以引爆的a点,就搜索a点能引爆的其他点。找火箭能引爆的点用二分
查找,已经排序了,只要找火箭范围内的左端点与右端点。然后找结构体中大于等于左端点的最小的点,小于等于右端点的最大下标。
要快速知道一个位置有没有雷,用map<pair<int, int>, int>
#include <iostream>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4+10, M = 2*N;
struct Node
{
int x, y, r, cnt; //(x, y):坐标, r:这个位置上雷的最大半径, cnt:这个位置上雷的个数
//按横纵坐标从小到大排序。也就是一纵队一纵队的
bool operator < (const Node& t)
{
if (t.x != x) return x < t.x;
return y < t.y;
}
}nodes[N]; //雷
int h[N], ne[M], e[N], idx; //e:编号
int n, m, num; //cnt:所有不重复雷的数量
map<pair<int, int>, int> mp; //记录每个位置上雷的编号
bool vi[N];
int res;
int sqr(int a) //sqrt 只能对 double,平方
{
return a*a;
}
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs2(int id) //id:引爆编号为id 雷的所有邻接点
{
vi[id] = true;
int ans = nodes[id].cnt;
for (int i = id; ~i; i = ne[i])
{
int j = e[i]; //编号
if (vi[j]) continue;
vi[j] = true;
ans += nodes[j].cnt;
}
return ans;
}
void dfs(int x, int y, int r)
{
//当前位置的左右节点no1, no2
Node no1 = {x-r, y, r}; //最左边的
Node no2 = {x+r, y, r}; //最右边的
int left = lower_bound(nodes+1, nodes+num+1, no1) - nodes; //找到大于等于左节点的最左边下标
int right = lower_bound(nodes+1, nodes+num+1, no2) - nodes; //找到小于等于右节点的最右边下标
//不加也没事
// //保证在范围内有解
// left = min(left, num);
// right = min(right, num);
for (int i = left; i <= right; i++)
{
int t = sqr(nodes[i].x - x) + sqr(nodes[i].y-y);
if (t <= sqr(r) && !vi[i]) //引爆这个雷的所有雷
res += dfs2(i);
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
//输入雷
for (int i = 1; i <= n; i++)
{
int x, y, r;
cin >> x >> y >> r;
if (!mp.count({x, y})) //若当前位置没有雷
{
num++; //下标从1开始
mp[{x, y}] = num;
nodes[num] = {x, y, r, 1};
}
else //若存在
{
int id = mp[{x, y}]; //雷在结构体中的下标
nodes[id].r = max(nodes[i].r, r);
nodes[id].cnt++;
}
}
sort(nodes+1, nodes+num+1); //下标从1开始
//建立雷的有向边
for (int i = 1; i <= num; i++)
{
auto t = nodes[i]; //当前地雷
int dist = sqr(t.r); //当前地雷距离的平方
//为了能提前break 掉不符合条件的解,我们就按x 左右讨论
for (int j = i-1; j >= 1; j--) //往左找,只要有左端点比当前雷的最远距离还远的就可以break
{
auto p = nodes[j];
if (sqr(p.x - t.x) > dist) break;
int d1 = sqr(p.x - t.x) + sqr(p.y - t.y); //曼哈顿距离
if (d1 <= dist)
add(i, j); //建立雷i -> j 的有向边
}
//找右边的
for (int j = i+1; j <= num; j++)
{
auto p = nodes[j];
if (sqr(p.x - t.x) > dist) break;
int d1 = sqr(p.x - t.x) + sqr(p.y - t.y); //曼哈顿距离
if (d1 <= dist)
add(i, j); //建立雷i -> j 的有向边
}
}
//输入火箭
for (int i = 0; i < m; i++)
{
int x, y, r;
cin >> x >> y >> r;
//遍历所有的雷,找火箭范围内能引爆的雷,再搜索这个雷的所有关联点
for (int j = 1; j <= num; j++)
dfs(x, y, r); //搜索这个火箭
}
cout << res;
return 0;
}