Jump lattice 跳格子_c++酷町喵在玩跳格子游戏,她在平地上沿直线从一点跳到另一点,起点在0处,终点在n处

题目描述

UpMing在玩一个小游戏：跳格子。

UpMing前方有一列格子共 N+1个，前 N个格子每个格子上都有一个数字1或者2，第 N+1个格子为终点。其中：

1:代表UpMing可以向后跳任意个格子。

2:代表UpMing可以向前跳最多D个格子（即可以跳1,2,3,...,D个格子）。

游戏开始时UpMing将走上第1个格子上，保证第一个格子上的数字一定为2。

现在，UpMing想找到一个最小的D能够使得他从第1个格子跳到第N+1个格子，但UpMing太懒了，他把这个问题交给了爱学习的Fox，Fox当场写了个代码，直接告诉了UpMing答案。

输入描述

第一行 一个整数N（1≤N≤1e5）。

第二行 N个整数,代表前 N个格子上的数字。

输出描述

一个整数，即最小的D。

样例

样例运行正确并不代表程序没有漏洞，判题服务将使用大量数据对你的程序进行评测。

输入 复制

4
2 1 1 2

输出 复制

3

答案 问题直接转换成2和2中间1的个数然后再加上1.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n],b[n]={0},j=0,max=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<n;i++)
    {
        if(a[i]==1)
        {
            b[j]++;
        }
        if(a[i]==2)
        j++;
        if(max<b[j])
        max=b[j];
    }
    cout<<max+1;
    return 0;
}