題目描述

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;
}

總結

以上是生活随笔為你收集整理的Jump lattice 跳格子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。