题意:有n个人,每个人都有长度不一样的爪子,所有人同时杀人,且只能杀在你前面的人(也就是数组小标比你小的人)

爪子长度的大小决定你可以杀在你前面的人数,问最后还剩多少人?

思路:这道题可以从最后面开始进行遍历,每次声明一个变量len把当前爪子当前所能够到的最前面的位置存进去,与前一个所能够到的位置(j - a[j])进行比较最小值,变量len就更新,循环不断判断当前位置是否大于len,循环一次就相当于杀一个人,最后再吧总人数减去杀掉的人数,就可以得到活下来的人数。

AC代码:

#include<stdio.h>
#define min(a, b) a<b?a:b
int a[1000005];
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	int tot = 0;
//一次遍历就够了 如果一直比较下去 当len=0或者i=0时候循环就结束 
	for(int i = n - 1; i >= 0; i--) {
		int len = i - a[i];
		for(int j = i - 1; j >= len && j >= 0; j--) {
			len = min(j - a[j], len);
			i = len;
			tot++;
		}
	}
	printf("%d\n", n - tot);
	return 0;
}