蔚破冲

用户名：dotcpp0673667

访问量：151

签　名：

等　　级
排　　名	47252
经　　验	308
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校	青岛科技大学
专　　业

　　自我简介：

TA的其他文章

扫雷 - 队列解法
浏览：136

你可能喜欢

扫雷 - 队列解法

　　作者: 蔚破冲　　　　发表时间：2024-04-05 11:31:42 浏览：136　|　评论：0　

原题链接：蓝桥杯2022年第十三届省赛真题-扫雷

思路 :
> 先将所有排雷火箭加入队列, 然后遍历所有未引爆的雷, 如果当前排雷火箭可以引爆
> 未引爆的雷，将未引爆的雷加入队列

时间复杂度 : 最坏 O(mn), 即每个排雷火箭都无法引爆任何雷

```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N = 1e5 + 10;
inline int read(){
    int f = 1, res = 0;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        res = res * 10LL + c - '0';
        c = getchar();
    }
    return res * f;
}
inline void write(int x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)  write(x / 10);
    putchar(x % 10 + '0');
}
int n, m;
struct boomer{
    int x, y, r;
}boomers[50010];
queue<boomer> q;
bool check(boomer &a, boomer &b){
    auto [x1, y1, r1] = a;
    auto [x2, y2, r2] = b;
    return (r1 * r1 >= (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
void solve(){
    n = read(); 
    m = read();
    for(int i = 1; i <= n + m; i ++){
        int x, y, r;
        x = read(), y = read(), r = read();
        if(i <= n) boomers[i] = {x, y, r};
        else q.push(boomer{x, y, r});
    }
    int res = 0;
    while(q.size()){
        auto t = q.front();
        q.pop();
        for(int i = res + 1; i <= n; i ++){
            if(check(t, boomers[i])){
                q.push(boomers[i]);
                res ++;
                swap(boomers[i], boomers[res]);
            }
        }
    }
   write(res);
}
 
signed main(){
    int T = 1;
    while (T --){
        solve();
    }
 
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

蔚破冲

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

剔除相关数（C语言代码）

C语言训练-最大数问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

扫雷 - 队列解法

评论区

精彩推荐

Tom数（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-求偶数和（C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言训练-自由落体问题（C语言代码）

金额的中文大写

简单的a+b （Java代码）

计算表达式

蔚破冲

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

剔除相关数 （C语言代码）

C语言训练-最大数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

扫雷 - 队列解法

评论区

精彩推荐

Tom数 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-求偶数和 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言训练-自由落体问题 （C语言代码）

金额的中文大写

简单的a+b （Java代码）

计算表达式

剔除相关数（C语言代码）

C语言训练-最大数问题（C语言代码）

　　评论区

Tom数（C语言代码）

C二级辅导-求偶数和（C语言代码）

C语言训练-自由落体问题（C语言代码）