問題：給定一個非重復正整數(shù)數(shù)組，表示“n”個人的穿越時間。這n個人站在橋的一側(cè)。Bridge 一次最多可容納兩個人。兩人過橋時，必須以較慢者的步調(diào)走。找出所有人可以過橋的最短總時間。我無法找到關于如何為“n”個人擴展它的模式。但不知何故，我設法找到了 4 個人的案子。有人可以幫我弄這個嗎。我是 Golang 的新手，我被這個問題困住了。package mainimport ( "fmt" "io/ioutil" "log" "os" "sort" "gopkg.in/yaml.v2")type conf struct { Person []map[string]float32 `yaml:"person"`}func (c *conf) getConf() *conf { filename := os.Args[1] // Taking file input yamlFile, err := ioutil.ReadFile(filename) // Yaml parse if err != nil { log.Printf("yamlFile.Get err #%v ", err) } err = yaml.Unmarshal(yamlFile, c) if err != nil { log.Fatalf("Unmarshal: %v", err) } return c}func main() { var c conf // Object of struct conf c.getConf() // calling getConf function // Sorting the current conf map n := map[float32][]string{} // Map to store current conf map var a []float32 // Store values from conf map for k, v := range c.Person { v := float32(v) fmt.Println(k, v) n[v] = append(n[v], k) } for k := range n { a = append(a, k) } // Converting float32 as float64 in order to sort the values in conf map float32AsFloat64Values := make([]float64, len(a)) for i, val := range a { float32AsFloat64Values[i] = float64(val) } sort.Float64s(float32AsFloat64Values) for i, val := range float32AsFloat64Values { a[i] = float32(val) } var time float32 fmt.Printf("\n%v\n", a) for _, k := range a { min1 := a[0] min2 := a[1] min3 := a[2]游樂場：https://play.golang.org/p/ObTVA8gk0mgConfig.yaml 是：person:
person_1: 2
person_2: 1
person_3: 5
person_4: 8
person_5: 9可以將其運行為：'go run main.go config.yaml'。我的情況是此 yaml 中可能有 4,5 或“n”個人。那么在給定約束的情況下，他們過橋的最短時間是多少。
2 回答
蕭十郎
TA貢獻1815條經(jīng)驗 獲得超13個贊
我認為原始問題比陳述的問題更有趣（是的，“Bridge and Torch”問題中必須有一個 Torch?。?/p>
基于維基百科的描述，例如，
四個人在夜里來到一條河邊。有一座狹窄的橋，但一次只能容納兩個人。他們只有一支手電筒，因為是晚上，過橋時必須使用手電筒。A 1 分鐘過橋，B 2 分鐘過橋，C 5 分鐘過橋，D 8 分鐘過橋。兩個人一起過橋的時候，一定要跟著慢的人走。問題是，如果火炬只持續(xù)15分鐘，他們能全部過橋嗎？
當然，在我們的例子中，有 N 個人而不是四個人，他們過橋所花的時間不定，但故事的其余部分是相同的。
這是實現(xià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 分鐘內(nèi)穿過
關鍵思想：
釋義：
令 X = [X1,X2,...,XN] 為交叉時間的排序數(shù)組，其中 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 考慮以下問題：如何讓兩個最慢的人（并且只有他們）過橋并在最短的時間內(nèi)帶回火炬。有兩種“好”的方法，時間?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}), 所以我們從這兩個中選擇最好的（最小的）
現(xiàn)在最慢的兩個已經(jīng)過橋，火炬在它開始的同一側(cè)，所以我們剩下 X' = [X1, X2, ..., X[N-2]] 的原始問題，可以通過應用相同的邏輯并對交叉時間求和來迭代求解
慕勒3428872
TA貢獻1848條經(jīng)驗 獲得超6個贊
問題：給定一個非重復正整數(shù)數(shù)組，表示“n”個人的穿越時間。這n個人站在橋的一側(cè)。Bridge 一次最多可容納兩個人。兩人過橋時，必須以較慢者的步調(diào)走。找出所有人可以過橋的最短總時間。
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 關注
- 234 瀏覽
添加回答
舉報
0/150
提交
取消