给定一个正数数组arr，代表每个人的体重。给定一个正数limit代表船的载重，所有船都是同样的载重量。
每个人的体重都一定不大于船的载重。
要求：
1, 可以1个人单独一搜船；
2, 一艘船如果坐2人，两个人的体重相加需要是偶数，且总体重不能超过船的载重；
3, 一艘船最多坐2人。
返回如果想所有人同时坐船，船的最小数量。
先排序，再按奇偶分成两个数组。对两个数组求船数，最后求和。
时间复杂度：排序的。
额外空间复杂度：O(N)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
arr := []int{1, 2, 3, 4, 5}
ret := minBoat(arr, 5)
fmt.Println(ret)
}
func minBoat(arr []int, limit int) int {
sort.Ints(arr)
odd := 0
even := 0
for _, num := range arr {
if (num & 1) == 0 {
even++
} else {
odd++
}
}
odds := make([]int, odd)
evens := make([]int, even)
for i := len(arr) - 1; i >= 0; i-- {
if (arr[i] & 1) == 0 {
even--
evens[even] = arr[i]
} else {
odd--
odds[odd] = arr[i]
}
}
return min(odds, limit) + min(evens, limit)
}
func min(arr []int, limit int) int {
if len(arr) == 0 {
return 0
}
N := len(arr)
if arr[N-1] > limit {
return -1
}
lessR := -1
for i := N - 1; i >= 0; i-- {
if arr[i] <= (limit / 2) {
lessR = i
break
}
}
if lessR == -1 {
return N
}
L := lessR
R := lessR + 1
noUsed := 0
for L >= 0 {
solved := 0
for R < N && arr[L]+arr[R] <= limit {
R++
solved++
}
if solved == 0 {
noUsed++
L--
} else {
L = getMax(-1, L-solved)
}
}
all := lessR + 1
used := all - noUsed
moreUnsolved := (N - all) - used
return used + ((noUsed + 1) >> 1) + moreUnsolved
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
