题意:有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;
}