304676: CF892B. Wrath

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Wrath

题意翻译

## 题目描述 那手上流着无辜之人的血的罪人啊! 有n个罪犯排成一排,其中第i个人拿着一个长 $L_{i}$ 的爪子。铃声敲响时每个人都会将其前面的一些人杀掉。所有人在同一时刻杀掉其他人。也就是说,如果$j<i$ 并且$j>=i-L_{i}$ ,那么第i个人将会杀掉第$j$ 个人。 现在给出每个爪子的长度,你要找出铃响之后还有多少人幸存。 ## 输入输出格式 ### 输入格式: 第一行包括一个整数$n$ $(1<=n<=10^6)$ 。 第二行包括$n$ 个整数$L_{1},L_{2},...,L_{n}(0<=L_{i}<=10^9)$ ### 输出格式: 输出一个整数,表示幸存的人的个数 ## 说明 第一个样例中,最后一个人杀掉他前面所有的人。 感谢@二元长天笑 提供的翻译

题目描述

Hands that shed innocent blood! There are $ n $ guilty people in a line, the $ i $ -th of them holds a claw with length $ L_{i} $ . 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-L_{i} $ . You are given lengths of the claws. You need to find the total number of alive people after the bell rings.

输入输出格式

输入格式


The first line contains one integer $ n $ ( $ 1<=n<=10^{6} $ ) — the number of guilty people. Second line contains $ n $ space-separated integers $ L_{1},L_{2},...,L_{n} $ ( $ 0<=L_{i}<=10^{9} $ ), where $ L_{i} $ is the length of the $ i $ -th person's claw.

输出格式


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

输入输出样例

输入样例 #1

4
0 1 0 10

输出样例 #1

1

输入样例 #2

2
0 0

输出样例 #2

2

输入样例 #3

10
1 1 3 0 0 0 2 1 0 3

输出样例 #3

3

说明

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

Input

题意翻译

## 题目描述 那手上流着无辜之人的血的罪人啊! 有n个罪犯排成一排,其中第i个人拿着一个长 $L_{i}$ 的爪子。铃声敲响时每个人都会将其前面的一些人杀掉。所有人在同一时刻杀掉其他人。也就是说,如果$j<i$ 并且$j>=i-L_{i}$ ,那么第i个人将会杀掉第$j$ 个人。 现在给出每个爪子的长度,你要找出铃响之后还有多少人幸存。 ## 输入输出格式 ### 输入格式: 第一行包括一个整数$n$ $(1<=n<=10^6)$ 。 第二行包括$n$ 个整数$L_{1},L_{2},...,L_{n}(0<=L_{i}<=10^9)$ ### 输出格式: 输出一个整数,表示幸存的人的个数 ## 说明 第一个样例中,最后一个人杀掉他前面所有的人。 感谢@二元长天笑 提供的翻译

加入题单

上一题 下一题 算法标签: