2021-06-27：给定一个正数数组arr，代表若干人的体重。再给定一个正数limit，表示所有船共同拥有的载重量。每艘船最多坐两人，且不能超过载重，想让所有的人同时过河，并且用最好的分配方法让船尽量少。返回最少的船数。
福大大 答案2021-06-27：
数组是[1 3 5 5 5 7 9 2 4 6 8 10]，limit是10。
1.排序。[1 3 5 5 5 7 9 2 4 6 8 10]排序后是[1 2 3 4 5 5 5 6 7 8 9 10]。
2.找到小于等于limit/2位置，，此时位置是6。
3.准备双指针，左指针指向6位置，右指针指向7位置。左右指针之和大于limit，左指针左移；左右指针之和小于limit，右指针右移；左右指针之和等于limit，左指针左移，右指针右移。
4.统计计数。左右能配对者，左右两个数计为1；不能配对者，左边每两个数计为1，右边1个数计为1。最后全部相加，就是需要返回的值。
时间复杂度：O（N）。额外空间复杂度：O（1）。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
arr := []int{1, 3, 5, 5, 5, 7, 9, 2, 4, 6, 8, 10}
fmt.Println(arr)
ret := minBoat(arr, 10)
fmt.Println(ret)
}
func minBoat(arr []int, limit int) int {
if len(arr) == 0 {
return 0
}
N := len(arr)
sort.Ints(arr)
fmt.Println(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
}
}
执行结果如下：
左神java代码
