8.14-T2捕老鼠（cat）

题目大意

有 N 个仓库，排成了一排，编号为 1～N。假设在第 i 个仓库点燃艾条，烟雾就会充满该仓库，并向左右扩散Ai的距离，接着所有|i-j|<=Ai的仓库 j 的老鼠被消灭。最少需要多少支艾条。

 

题解

贪心的策略

不断找右端点最靠右()，且可以和之前选过的线段相连的线段，ans++。

时间复杂度O(nlogn到n^2之间？？！)

但也能过...

 

#include<bits/stdc++.h>

using namespace std;

inline int read()

{

    int sum = ,p = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

        if(ch == '-')

            p = -;

        ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

        (sum *= ) += ch - '';

        ch = getchar();

    }

    return sum * p;

}

const int N = 5e5 + ;

int n,ans;

struct edge

{

    int l,r;

} e[N];

int main()

{

    freopen("cat.in","r",stdin);

    freopen("cat.out","w",stdout);

    n = read();

    for(int i = ; i <= n; i++)

    {

        int a = read();

        e[i].l = max(,i - a);

        e[i].r = min(n,i + a);

    }

    int far = ,now = ,mid;

    while(now <= n)

    {

        far = ;

        for(int i = ;i <= n;i++)

        {

            if(e[i].l <= now && e[i].r >= now)

                if(far < e[i].r)

                    far = e[i].r;

        }

        now = far + ;

        ans++;

    }

    printf("%d\n",ans);

    return ;

}