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]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)

在這裡插入圖片描述