2021-04-17:给定一个整型数组 arr,数组中的每一个值都为正数,表示完成一幅画做须要的时间,再 给定 一个整数 num,表示画匠的数量,每一个画匠只能画连在一块儿的画做。全部的画家 并行工做,请

2021-04-17:给定一个整型数组 arr,数组中的每一个值都为正数,表示完成一幅画做须要的时间,再 给定 一个整数 num,表示画匠的数量,每一个画匠只能画连在一块儿的画做。全部的画家 并行工做,请 返回完成全部的画做须要的最少时间。【举例】arr=[3,1,4],num=2。最好的分配方式为第一个画匠画 3 和 1,所需时间为 4。第二个画匠画 4,所需时间 为 4。 由于并行工做,因此最少时间为 4。若是分配方式为第一个画匠画 3,所需时 间为 3。第二个画 匠画 1 和 4,所需的时间为 5。那么最少时间为 5,显然没有第一 种分配方式好。因此返回 4。arr=[1,1,1,4,3],num=3。最好的分配方式为第一个画匠画前三个 1,所需时间为 3。第二个画匠画 4,所需时间 为 4。 第三个画匠画 3,所需时间为 3。返回 4。java

福大大 答案2021-04-17:git

二分法。github

代码用golang编写。代码以下:golang

package main

import (
    "fmt"
    "math"
)

func main() { 
    arr := []int{ 2, 6, 3, 5}
    M := 2
    ret := splitArray3(arr, M)
    fmt.Println(ret)
}
func splitArray3(nums []int, M int) int { 
    sum := int64(0)
    for i := 0; i < len(nums); i++ { 
        sum += int64(nums[i])
    }
    l := int64(0)
    r := int64(sum)
    ans := int64(0)
    for l <= r { 
        mid := int64((l + r) / 2)
        cur := getNeedParts(nums, mid)
        if cur <= M { 
            ans = mid
            r = mid - 1
        } else { 
            l = mid + 1
        }
    }
    return int(ans)
}
func getNeedParts(arr []int, aim int64) int { 
    for i := 0; i < len(arr); i++ { 
        if int64(arr[i]) > aim { 
            return math.MaxInt32
        }
    }
    parts := 1
    all := arr[0]
    for i := 1; i < len(arr); i++ { 
        if int64(all+arr[i]) > aim { 
            parts++
            all = arr[i]
        } else { 
            all += arr[i]
        }
    }
    return parts
}

执行结果以下:
图片数组


左神java代码
力扣410. 分割数组的最大值url

相关文章
相关标签/搜索