2021-06-27：给定一个正数数组arr，代表若干人的体重。再给定一个正数limit，表示所有船共同拥有的载重量。每艘船最多

福大大架构师每日一题

发布于 2021-08-05 16:13:19

3480

发布于 2021-08-05 16:13:19

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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
    }
}

执行结果如下：