机器人正在玩一个古老的基于 DOS 的游戏。
游戏中有 N+1座建筑——从 0 到 N 编号，从左到右排列。
编号为 0 的建筑高度为 0 个单位，编号为 i 的建筑高度为 H(i)
个单位。
起初，机器人在编号为 0 的建筑处。
每一步，它跳到下一个（右边）建筑。
假设机器人在第 k 个建筑，且它现在的能量值是 E ，下一步它将跳到第 k+1
个建筑。
如果 H(k+1)>E ，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到
E−H(k+1) 的能量值。
游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。
现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？
输入格式
第一行输入整数 N 。
第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N) 代表建筑物的高度。
输出格式
输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。
数据范围
\(1≤N,H(i)≤10^5\),
输入样例1：
输出样例1：
输入样例2：
输出样例2：
输入样例3：
输出样例3：
分析
为什么这题可以联想到二分呢？因为如果找打一个E(0)的最小值，那么所有比E(0)大的值就一定满足题意，所有比E(0)小的值就一定不满足
另外，一定不要忽视第0栋楼的
当跳到第i栋楼时，能量与楼层的关系
结合代码分析
代码
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
26
27
28
29
30
31
32
33
34
35
| import java.util.Scanner;
public class Main {
static int MAXHEIGHT = (int)1e5 + 10;
static int[] building = new int[MAXHEIGHT];
static int[] energy = new int[MAXHEIGHT];
static int maxHeight = 0;
static boolean check(int startEnergy, int n) {
energy[0] = startEnergy;
for(int i = 1; i <= n; i++) {
energy[i] = 2 * energy[i - 1] - building[i];
if(energy[i] > maxHeight) return true;
if(energy[i] < 0) return false;
}
return true;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 1; i <= n; i++) {
building[i] = scan.nextInt();
if(building[i] > maxHeight) {
maxHeight = building[i];
}
}
int start = 0, end = maxHeight;
while(start < end) {
int mid = (start + end) / 2;
if(check(mid, n)) end = mid;
else start = mid + 1;
}
System.out.println(start);
scan.close();
}
}
|