#113. 2017GCOI六年级第六题 幸存者(2.3)
2017GCOI六年级第六题 幸存者(2.3)
说明
有 n 个人,现在他们从左往右站成一列。第 i 个人的位置为 i,且第 i 个人手里握着一把长度为 L[i]的大刀。指挥者统一指令, n 个人一齐往左边砍去。对于位置为 i, j 的两个人(i<j),如果满足 i ≥ j - L[j],那么位置为 i的人就会被位置为 j 的人砍死。问:最后有几个人生存下来?输入格式
第一行输入一个整数 n(1≤n≤1000000),表示有 n 个人。第二行输入 n 个整数,第 i 个整数是 Li(0≤L[i]≤1000000000), L[i]表示第 i个人的大刀长度
输出格式
输出一个整数,表示最后生存下来的人数样例
提示
样例三生存下来的是:第3、4、10个。