2021-12-01：给定一个正数数组arr，代表每个人的体重。给

原创

福大大架构师每日一题

发布于 2021-12-01 22:43:36

2290

发布于 2021-12-01 22:43:36

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

2021-12-01：给定一个正数数组arr，代表每个人的体重。给定一个正数limit代表船的载重，所有船都是同样的载重量。

每个人的体重都一定不大于船的载重。

要求：

1, 可以1个人单独一搜船；

2, 一艘船如果坐2人，两个人的体重相加需要是偶数，且总体重不能超过船的载重；

3, 一艘船最多坐2人。

返回如果想所有人同时坐船，船的最小数量。

来自腾讯。

答案2021-12-01：

先排序，再按奇偶分成两个数组。对两个数组求船数，最后求和。

时间复杂度：排序的。

额外空间复杂度：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
    }
}

执行结果如下：