jump--不跳脏楼梯

2017-10-16 11:14:46来源:CSDN作者:JingleLiA人点击

分享

题目描述

小男孩Petya非常喜欢楼梯。但是他从简单的上下去无聊,他一次又喜欢跳上几层楼梯。当他站在一些楼梯上时,他可以跳到下一个楼梯,或者一次跳过一两个楼梯。
但是一些楼梯太脏了,Petya不想踩踏他们。现在Petya在楼梯的第一层,由n个楼梯组成。他也知道这个楼梯的肮脏楼梯的数量。帮助Petya找出他是否可以跳过整个
楼梯,到达最后的楼梯号码n,而不用肮脏的楼梯一次。

输入

第一行包含两个整数n和m(1≤n≤10000000,0≤m≤3000) 楼梯中的楼梯数量和肮脏楼梯的数量。第二行包含m个不同的空格分隔的整数d1,d2,...,dm(1≤di≤n)  
脏楼梯的阶数(以任意顺序)。

输出

打印“YES”,如果Petya可以达到楼梯号n,只能在干净的楼梯上踩踏。否则打印“NO”。

样例输入

10 52 4 8 3 6

样例输出

NO

提示

import java.util.*;public class Main {    static Scanner in=new Scanner(System.in);    static int n,m;    static int[] dir = new int[10000000];	public static void main(String[] args) {				while(in.hasNext()){			Arrays.fill(dir, 0);			n= in.nextInt();			m= in.nextInt();			int t=0;			boolean f = false;			for (int i = 1; i <= m; i++) {				t=in.nextInt();			    dir[t]=1; 			    if(t==n||t==1)			      f=true;		    }			if(f)				System.out.println("NO");		   else{            for (int i = 1; i <= n-2 ; i++){			  if(dir[i]==1&&dir[i+1]==1&&dir[i+2]==1){				  f=true;			      break;			   }  		   }            if(f)	          System.out.println("NO");            else        	 System.out.println("YES");           }        }				}}
 
分析:由题意可知,小明不能连续跳三个脏楼梯,即脏楼梯的序列不能有三个连续的数字,那么就好解决了,我用的是一个标志数组    另外需要注意的一点是第一个和最后一个楼梯也不能是脏楼梯,我第一次每过就是因为没考虑到1,连n都想到了,真是。。。。)

微信扫一扫

第七城市微信公众平台