730. 机器人跳跃问题
摘要
Title: 730. 机器人跳跃问题
Tag: 二分
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
730. 机器人跳跃问题
-
题意
机器人正在玩一个古老的基于 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 个建筑，在这个过程中能量值不能为负数个单位。
现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？ -
思路
二分即可，能量值的范围在[0, max]之间
-
代码
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'''
Author: NEFU AB-IN
Date: 2022-03-22 20:11:59
FilePath: \ACM\Acwing\730.py
LastEditTime: 2022-03-22 20:12:00
'''
def check(e):
for i in range(n):
if a[i] > e:
e -= (a[i] - e)
else:
e += (e - a[i])
return e >= 0
n = int(input())
a = list(map(int, input().split()))
l, r = 0, max(a)
while l < r:
mid = l + r >> 1
if check(mid):
r = mid
else:
l = mid + 1
print(r)