AcWing 730. 机器人跳跃问题

Problem: AcWing 730. 机器人跳跃问题

文章目录

• 思路
• 解题方法
• 复杂度
• Code

思路

这是一个二分查找的问题。我们需要找到机器人的最小初始能量，使得它能够完成所有的跳跃。我们可以通过二分查找来找到这个最小的初始能量。我们从最小能量1开始，到最大能量100000（因为题目中给出的高度最大为100000），然后在这个范围内进行二分查找。对于每一个中间值，我们检查机器人是否能够完成所有的跳跃。如果能，我们就将右边界移动到中间值的左边，否则我们将左边界移动到中间值的右边。最后，我们找到的左边界就是我们需要的最小初始能量。

解题方法

我们使用二分查找的方法来解决这个问题。对于每一个中间值，我们模拟机器人的跳跃过程，检查机器人是否能够完成所有的跳跃。我们从机器人的初始能量开始，每次跳跃后，机器人的能量会变为2倍，然后减去跳跃的高度。如果在任何时候，机器人的能量变为负数，那么我们就知道这个初始能量是不够的，我们需要增大初始能量。如果机器人的能量在所有的跳跃后都没有变为负数，那么我们就知道这个初始能量是足够的，我们需要减小初始能量。

复杂度

时间复杂度:

二分查找的时间复杂度为 O ( l o g n ) O(logn) O(logn)，对于每一个中间值，我们需要 O ( n ) O(n) O(n)的时间来模拟机器人的跳跃过程，所以总的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。

空间复杂度:

我们只需要常数的空间来存储机器人的能量和跳跃的高度，所以空间复杂度为 O ( 1 ) O(1) O(1)。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int MAXN = (int) (1e5 + 10);
	static int[] arr = new int[MAXN];
	static int n;

	public static void main(String[] args) throws IOException {
		n = nextInt();
		for (int i = 1; i <= n; i++) {
			arr[i] = nextInt();
		}
		int l = 1, r = (int) (1e5), ans = 0;
		while (l <= r) {
			int mid = (l + r + 2 - 1) / 2;
			if (deal(mid)) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		out.println(ans);
		out.flush();
	}

	private static boolean deal(int e) {
		// TODO Auto-generated method stub
		for(int i = 1; i <= n; i++) {
			e = 2 * e - arr[i];
			if(e < 0) {
				return false;
			}
			if(e > MAXN - 10) {
				return true;
			}
		}
		return true;
	}

	static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}