首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

2024-01-31:用go语言,机器人正在玩一个古老的基于DOS的游戏, 游戏中有N+1座建筑,从0到N编号,从左到右排列,

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)

在这里插入图片描述

  • 发表于:
  • 原文链接https://page.om.qq.com/page/OjFq4Wic-wPbiij34iADcaIw0
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

相关快讯

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券