2 回答
TA贡献1815条经验 获得超13个赞
我认为原始问题比陈述的问题更有趣(是的,“Bridge and Torch”问题中必须有一个 Torch!)。
基于维基百科的描述,例如,
四个人在夜里来到一条河边。有一座狭窄的桥,但一次只能容纳两个人。他们只有一支手电筒,因为是晚上,过桥时必须使用手电筒。A 1 分钟过桥,B 2 分钟过桥,C 5 分钟过桥,D 8 分钟过桥。两个人一起过桥的时候,一定要跟着慢的人走。问题是,如果火炬只持续15分钟,他们能全部过桥吗?
当然,在我们的例子中,有 N 个人而不是四个人,他们过桥所花的时间不定,但故事的其余部分是相同的。
这是实现:
import (
"fmt"
"sort"
)
func minCrossingTime(x []int) int {
if len(x) == 1 {
return x[0]
}
sort.Ints(x)
t := 0
a, b := x[0], x[1]
x = x[2:]
for len(x) >= 2 {
n := len(x)
c, d := x[n-2], x[n-1]
x = x[:n-2]
t1 := 2*b + a + d
t2 := d + c + 2*a
if t1 < t2 {
t += t1
} else {
t += t2
}
}
if len(x) == 1 {
c := x[0]
t += a + b + c
} else {
t += b
}
return t
}
func main() {
x1 := []int{1, 2, 5, 8}
fmt.Printf("x = %x, time = %d\n", x1, minCrossingTime(x1))
x2 := []int{3, 8, 1, 6, 2, 9}
fmt.Printf("x = %x, time = %d\n", x2, minCrossingTime(x2))
}
输出:
x = [1 2 5 8], time = 15
x = [1 2 3 6 8 9], time = 27
注意:第一个例子 [1 2 5 8] 直接来自维基百科,所以答案是肯定的,他们可以在 15 分钟内穿过
关键思想:
释义:
令 X = [X1,X2,...,XN] 为交叉时间的排序数组,其中 X1 最快,XN 最慢
让我们将 XI 和 XJ 这对人交叉表示为 {XI,XJ},XK 人交叉为 {XK},+{...} 表示在所需方向上交叉,-{...} 在相反的方向
逻辑:
如果 N < 4 问题很简单:
N = 1 => t = X1 (+{X1})
N = 2 => t = X2 (+{X1,X2})
N = 3 => t = X1 + X2 + X3 (+{X1,X2} -{X1} + {X1,X3})
如果 N >= 4 考虑以下问题:如何让两个最慢的人(并且只有他们)过桥并在最短的时间内带回火炬。有两种“好”的方法,时间 t1 = X1 + 2*X2 + XN
(+{X1,X2} -{X1} +{X[N-1],XN} -{X2}) 和 (+ t2 = 2*X1 + X[N-1] + XN
{X1,X[N- 1]} -{X1} +{X1,XN} -{X1}), 所以我们从这两个中选择最好的(最小的)
现在最慢的两个已经过桥,火炬在它开始的同一侧,所以我们剩下 X' = [X1, X2, ..., X[N-2]] 的原始问题,可以通过应用相同的逻辑并对交叉时间求和来迭代求解
TA贡献1848条经验 获得超6个赞
问题:给定一个非重复正整数数组,表示“n”个人的穿越时间。这n个人站在桥的一侧。Bridge 一次最多可容纳两个人。两人过桥时,必须以较慢者的步调走。找出所有人可以过桥的最短总时间。
person:
person_1: 2
person_2: 1
person_3: 5
person_4: 8
person_5: 9
你的算法看起来很复杂。
例如,
package main
import (
"fmt"
"sort"
)
func minCrossingTime(people []int) int {
sort.Slice(people, func(i, j int) bool {
return people[i] > people[j]
})
min := 0
for i := 0; i < len(people); i += 2 {
min += people[i]
}
return min
}
func main() {
people := []int{2, 1, 5, 8, 9}
fmt.Println(len(people), people)
crossingTime := minCrossingTime(people)
fmt.Println(len(people), people)
fmt.Println(crossingTime)
}
游乐场:https://play.golang.org/p/pXdGcinwxr-
输出:
5 [2 1 5 8 9]
5 [9 8 5 2 1]
15
- 2 回答
- 0 关注
- 163 浏览
添加回答
举报