文章
18
粉丝
0
获赞
100
访问
3.2k
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int num[100005];
int max(int x,int y)
{
return x>y?x:y;
}
int jump(int n,int* num)//核心代码块,n是数组长度,后面传入数组
{
int count=0;//计数
//2 3 1 1 4为例子
int curmax=num[0];//当前的覆盖范围
int nextmax = 0;//当前的覆盖内,数的覆盖范围范围
for(int i=0;i<n-1;i++)
{
//当前的覆盖范围。num[0]=2的话,当前能覆盖的范围就是[0,2]。
//我们的思路一直是遍历当前数的覆盖范围里面每个数的最大范围,然后取最大值。
//比如curmax=2;那num[1]的覆盖范围就是1+num[1]= 4就是能从当前下标1覆盖到下标4;num[2]的覆盖是1+num[2]=3
nextmax = max(i+num[i],nextmax);
if(i==curmax)//这里我们遍历到当前数num[0]的最大覆盖范围,也就是下标2的位置。我们要判断一下到终点了吗
{
if(curmax!=n-1)//如果没有到终点
{
if(curmax ==nextmax)//到不了终点,下标0到i的nextmax最大覆盖范围就是当前覆盖范围
return -1;
count++;
curmax=nextmax;//如果下标0-i有内的最大覆盖范围有比当前最大覆盖范围大就换车;
}
}
}
return count;
}
int main()
{
int t;
scanf("%d",&t);
for(int i=0;i<t;i++)
{
int n;
scanf("%d",&n);
for(int j=0;j<n;j++)
{
scanf...
登录后发布评论
暂无评论,来抢沙发