補題---892B-Wrath(cf)[2018-3-16]BNUZ套題比賽div2

B - Wrath    

CodeForces - 892B 

Hands that shed innocent blood!

There are n guilty people in a line, the i-th of them holds a claw with length Li. The bell rings and every person kills some of people in front of him. All people kill others at the same time. Namely, the i-th person kills the j-th person if and only if j < i and j ≥ i - Li.

You are given lengths of the claws. You need to find the total number of alive people after the bell rings.

Input

The first line contains one integer n (1 ≤ n ≤ 106) — the number of guilty people.

Second line contains n space-separated integers L1, L2, ..., Ln (0 ≤ Li ≤ 109), where Li is the length of the i-th person's claw.

Output

Print one integer — the total number of alive people after the bell rings.

Example Input

4
0 1 0 10
      

Output

1
      

Input

2
0 0
      

Output

2
      

Input

10
1 1 3 0 0 0 2 1 0 3
      

Output

3
      

Note

In first sample the last person kills everyone in front of him

比賽的時候寫題太慢，這道題寫都沒有寫，很失敗；-；

于是在課後補題時，内心還懷揣着一絲最後的倔強，想着要自己寫出來

然而測試資料時頻頻時間超限，無法通過

萬分難過

于是看了一眼别人的答案：哇，真是簡單

更加難過了

首先是自己的代碼:

#include <stdio.h>
#define MAXN 1000005
int a[MAXN],b[MAXN];
int main()
{
	int n,k,c;
	while(~scanf("%d",&n))
	{
		k=0;
		c=1;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			b[i]=1;
			k++;
			if(a[i]>0&&i!=1)
			{
				if(a[i]>=i-1)
				{
					k=1;
					c=i;
					continue;
				}
				for(int j=i-1;j>i-1-a[i]&&j>=c;j--)
				{
					if(k==1)
						break;	
					else if(b[j]==1)
					{
						k--;
						b[j]=0;
					}
				}
			}
		}
		printf("%d\n",k);
	}
} 
           

qaq接下來是别人的：

//忘記是哪來的了（如侵删

#include <stdio.h>
#define MAXN 1000005
int a[MAXN],b[MAXN];
int main()
{
	int n,ans;
	while(~scanf("%d",&n))
	{
	    ans=n;
	    for(int i=1;i<=n;i++)
	    {
		scanf("%d",&a[i]);
	    }
	    int ans=0;  
    	    int tmp=n+1;  
    	    for(int i=n;i>=1;i--)
	    {  
     	        if(i<tmp) ans++;  // 如果目前這個人在上一個人的爪長度攻擊範圍之外，存活
      	        if(tmp>=i-a[i]) tmp=i-a[i]; // 一輪攻擊後目前剩餘的人數
    	    }  
	    printf("%d\n",ans);
	}
}