June 27, 2021: given a positive array arr, it represents the weight of several people

2021-06-27： Given an array of positive numbers arr, Represents the weight of several people . Give me a positive number limit, Indicates the deadweight shared by all ships . A maximum of two people can sit on each ship , And shall not exceed the load , I want all the people to cross the river at the same time , And use the best allocation method to minimize the number of ships . Returns the minimum number of ships .

Fuda answer 2021-06-27：

An array is 1 3 5 5 5 7 9 2 4 6 8 10,limit yes 10.

1. Sort .1 3 5 5 5 7 9 2 4 6 8 10 After sorting 1 2 3 4 5 5 5 6 7 8 9 10.

2. Find less than or equal to limit/2 Location ,, At this time, the position is 6.

3. Prepare double pointer , The left pointer points to 6 Location , The right pointer points to 7 Location . The sum of the left and right pointers is greater than limit, The left pointer moves to the left ; The sum of the left and right pointers is less than limit, Right pointer moves right ; The sum of the left and right hands equals limit, The left pointer moves to the left , Right pointer moves right .

4. Statistics count . Left and right can be matched , The left and right numbers are calculated as 1; Those who cannot be paired , Every two numbers on the left count as 1, On the right 1 Count as 1. Add them all at last , Is the value that needs to be returned .

Time complexity ：O（N）. Extra space complexity ：O（1）.

The code to use golang To write . The code is as follows ：

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

The results are as follows ：

picture

---

Zuo Shen java Code