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：
來自左承雲。
敏捷 351.首先，根據給定的輸入陣列將變數 n 初始化為第乙個元素的值（即建築物的數量）。
2.初始化變數 l（左邊界）、r（右邊界）、max（最大高度）為 0。
3.通過迴圈 n 次，輸入中的建築物高度按順序儲存在陣列 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 是否為非負值且不超過最大高度最大值，然後遍歷建築物。
5.2.2.如果總和小於或等於當前建築高度 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）。 由於最大高度最大值是在穿越建築物時計算的，因此總時間複雜度為 o（n log h）。
總附加空間複雜度：o（n），其中 n 是乙個常數，陣列 arr 是最大值，maxn 是更大的常數。
package mainimport ( "fmt")const maxn = 100001var arr [maxn]intvar n intfunc main() ii := 0 n = inputs[ii] ii++ l := 0 r := 0 max := 0 for i := 0; i < n; i++ m, ans := 0, -1 for l <= r else }fmt.println(ans)}func ok(sum, max int) bool else }return sum >= 0}func max2(a, b int) int return b}
在此處插入說明。
# -*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 >= 0def max2(a, b): return a if a > b else bmaxn = 100001arr = [0] *maxninputs = [5, 3, 4, 3, 2, 4]ii = 0n = 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 = rm, ans = 0, -1while l <= r: m = (l + r) // 2 if ok(m, max_val): ans = m r = m - 1 else: l = m + 1print(ans)
在此處插入說明。