1855. 愤怒的奶牛

题目链接
https://www.acwing.com/problem/content/1857/

解析

一个一维的bfs+暴力，暴力枚举每一个最开始击中的点，然后通过bfs把所有符合要求的点加进队列，然后更新下一轮的点。需要注意的有两点：

• 统计会爆炸的点的个数：将每个会爆炸的点加进队列，在每个点出队列的时候记一个cnt就行；不要只加入每轮引爆最左边和最右边的点，这样可能是不全面的。

• 学习怎么一轮一轮地改变爆炸范围

Ac代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

const int N = 110;

int cnt;
int start, n;
queue<int> q;
int a[N];
bool st[N];
map<int, int> mp;

void bfs(int x)
{
    cnt = 0;
    memset(st, 0, sizeof st);
    mp[x] = 1;
    q.push(x);
    st[x] = true;

    int right, left;
    while(q.size())
    {
        int s = q.front(); q.pop();
        cnt ++;
        left = s - 1, right = s + 1;

        while(left >= 1 && a[s] - a[left] <= mp[s]) {
            if(st[left]) left --;
            else{
                q.push(left);
                st[left] = true;
                mp[left] = mp[s] + 1;
                left --;
            }
        }

        while(right <= n && a[right] - a[s] <= mp[s]) {
            if(st[right]) right ++;
            else{
                q.push(right);
                st[right] = true;
                mp[right] = mp[s] + 1;
                right ++;
            }
        }
    }
    return;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);

    int ans = 0;
    for(int i = 1; i <= n; i ++){
        bfs(i);
        ans = max(ans, cnt);
    }
    printf("%d\n", ans);

    return 0;
}