2024-01-31：用go语言，机器人正在玩一个古老的基于DOS的游戏， 游戏中有N+1座建筑，从0到N编号
0 / 0 / 创建于 1年前
moonfdd 的个人博客
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：
来自左程云。
大体步骤如下：#
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]int
var 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 = 100001
arr = [0] * MAXN
inputs = [5, 3, 4, 3, 2, 4]
ii = 0
n = inputs[ii]
ii += 1
l = 0
r = 0
max_val = 0
for i in range(n):
arr[i] = inputs[ii]
ii += 1
r = max2(r, arr[i])
max_val = r
m, ans = 0, -1
while l <= r:
m = (l + r) // 2
if ok(m, max_val):
ans = m
r = m - 1
else:
l = m + 1
print(ans)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：