机器人跳跃问题

在这里插入图片描述

求解代码

Main方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


	public static int MAXN = 100001;

	public static int[] arr = new int[MAXN];

	public static int n;

	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while(in.nextToken()!=StreamTokenizer.TT_EOF){
			n = (int)in.nval;
			int l = 0;
			int r = 0;
			for(int i=1;i<=n;i++){
				in.nextToken();
				arr[i]=(int)in.nval;
				r=Math.max(r,arr[i]);
			}
			out.println(compute(l,r,r));
		}
		out.flush();
		out.close();
		br.close();
	}

compute方法

区间[l,r]表示通关所需要的最小的能量范围， max表示所有建筑的最大高度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


	public static int compute(int l,int r,int max){
		int m,ans = -1;
		while(l<=r){
			m = l+((r-l)>>1);
			if(f(m,max)){
				ans = m;
				r=m-1;
			}else{
				l=m+1;
			}
		}
		return ans;
	}

f方法

初始能量设置为energy，max是建筑的最大高度，这里有个需要注意的点就是：

初始能量越小，它就越吃亏，遇到比它高的建筑，它减小的更快；遇到比它低的建筑，增加的也更慢。

一旦能量超过了建筑高度的最大值，肯定可以通关，可以直接返回。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


public static boolean f(int energy,int max){
		for(int i=1;i<=n;i++){
			if(energy<=arr[i]){
				energy-=arr[i]-energy;
			}else{
				energy+=energy-arr[i];
			}

			if(energy>=max){
				return true;
			}

			if(energy<0){
				return false;
			}
		}
		return true;
	}