2024-01-31：用 go 语言，机器人正在玩一个古老的基于 DOS 的游戏，游戏中有 N+1 座建筑，从 0 到 N 编号，从左到右排列，编号为 0 的建筑高度为 0 个单位，编号为 i 的建筑的高度为 H(i) 个单位，起

作者：福大大架构师每日一题

2024-01-31
北京
本文字数：1616 字
阅读完需：约 5 分钟

2024-01-31：用 go 语言，机器人正在玩一个古老的基于 DOS 的游戏，

游戏中有 N+1 座建筑，从 0 到 N 编号，从左到右排列，

编号为 0 的建筑高度为 0 个单位，编号为 i 的建筑的高度为 H(i)个单位，

起初，机器人在编号为 0 的建筑处，

每一步，它跳到下一个（右边）建筑。假设机器人在第 k 个建筑，且它现在的能量值是 E，

下一步它将跳到第个 k+1 建筑，

它将会得到或者失去正比于与 H(k+1)与 E 之差的能量，

如果 H(k+1) > E 那么机器人就失去 H(k+1)-E 的能量值，否则它将得到 E-H(k+1)的能量值，

游戏目标是到达第个 N 建筑，在这个过程中，能量值不能为负数个单位。

现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏。

来自字节。

答案 2024-01-31：

来自左程云。

灵捷3.5

大体步骤如下：

1.首先，根据给定的输入数组 inputs，初始化变量 n 为第一个元素的值（即建筑数量）。

2.初始化变量 l（左边界）、r（右边界）、max（最大高度）为 0。

3.通过循环遍历 n 次，将 inputs 中的建筑高度依次存储到数组 arr 中，并更新 r 为当前最大高度。

4.初始化变量 m 为 0，ans 为-1。这两个变量将用于记录二分搜索的结果。

5.进行二分搜索，当左边界 l 小于等于右边界 r 时，执行以下步骤：

5.1.计算中间值 m 为(l + r) / 2。

5.2.调用函数 ok(m, max)判断以 m 为能量值是否能完成游戏：

5.2.1.在循环中，检查当前能量值 sum 是否非负且不超过最大高度 max，并遍历建筑。

5.2.2.如果 sum 小于等于当前建筑高度 arr[i]，则机器人失去(arr[i] - sum)的能量。

5.2.3.否则，机器人得到(sum - arr[i])的能量。

5.2.4.如果 sum 仍然非负，则返回 true 表示以 m 为能量值可以完成游戏，否则返回 false。

5.3.如果 ok(m, max)返回 true，更新 ans 为 m，并将右边界 r 更新为 m-1。

5.4.否则，将左边界 l 更新为 m+1。

6.输出结果 ans，即最低能量值开始游戏可以保证成功完成游戏。

总的时间复杂度：O(n log H)，其中 n 为建筑数量，H 为最大高度。因为进行了一次二分搜索，每次判断所需的时间复杂度为 O(n)，而循环内部还需要遍历建筑，总时间复杂度为 O(n)。由于最大高度 max 是在遍历建筑时计算得到的，因此总时间复杂度为 O(n log H)。

总的额外空间复杂度：O(N)，其中 N 为常数，数组 arr 的大小为 MAXN，而 MAXN 为一个较大的常数。

go 完整代码如下：

package main
import (  "fmt")
const MAXN = 100001
var arr [MAXN]intvar n int
func main() {  inputs := []int{5,    3, 4, 3, 2, 4}  ii := 0
  n = inputs[ii]  ii++  l := 0  r := 0  max := 0  for i := 0; i < n; i++ {    arr[i] = inputs[ii]    ii++    r = max2(r, arr[i])    max = r  }
  m, ans := 0, -1  for l <= r {    m = (l + r) / 2    if ok(m, max) {      ans = m      r = m - 1    } else {      l = m + 1    }  }
  fmt.Println(ans)
}
func ok(sum, max int) bool {  for i := 0; i < n && sum >= 0 && sum <= max; i++ {    if sum <= arr[i] {      sum -= arr[i] - sum    } else {      sum += sum - arr[i]    }  }  return sum >= 0}
func max2(a, b int) int {  if a > b {    return a  }  return b}

复制代码

python 完整代码如下：

# -*-coding:utf-8-*-
def ok(sum, max_val):    for i in range(n):        if sum >= 0 and sum <= max_val:            if sum <= arr[i]:                sum -= arr[i] - sum            else:                sum += sum - arr[i]        else:            break    return sum >= 0

def max2(a, b):    return a if a > b else b

MAXN = 100001arr = [0] * MAXN
inputs = [5, 3, 4, 3, 2, 4]ii = 0
n = inputs[ii]ii += 1l = 0r = 0max_val = 0for i in range(n):    arr[i] = inputs[ii]    ii += 1    r = max2(r, arr[i])    max_val = r
m, ans = 0, -1while l <= r:    m = (l + r) // 2    if ok(m, max_val):        ans = m        r = m - 1    else:        l = m + 1
print(ans)