300ms 解法

#include<bits/stdc++.h>
//这是300ms的代码
using namespace std;
 
struct node{int l, r;}s[500010];
//按灭鼠范围的左边界由小到大排序，相同则按右边界由小到大排序 
bool cmp(node s1, node s2){if(s1.l!=s2.l) return s1.l<s2.l;else return s1.r<s2.r;}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a;scanf("%d",&a);
        s[i].l=max(i-a,1);
        s[i].r=min(i+a,n);
    }
    sort(s+1,s+n+1,cmp);
    int cnt=0, now=0, i=1; 
    while(now<n)//本次搜索时，1~now的老鼠已经被消灭
    {
        int maxr=0;//maxr 记录最远的右边界 
        while(s[i].l<=now+1&&i<=n)
        {
            if(s[i].r>maxr) maxr=s[i].r;
            i++;
        }
        now=maxr;
        cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}

60ms 优化解法

#include<bits/stdc++.h>
//这是60ms的代码
using namespace std;
const int N=500005;
int a[N],n,dp[N];
int main()
{
    int t;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),t=max(i-a[i],1),dp[t]=max(dp[t],i+a[i]);
    for(int i=1;i<=n;i++) dp[i]=max(dp[i],dp[i-1]);
    int ans=0,i=0,lim=dp[1];
    while(i<n)
    {
        i=lim;
        lim=dp[i+1];
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}