• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

互联网 diligentman 9个月前 (04-17) 45次浏览

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。

福大大 答案2021-04-17:

二分法。

代码用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
}

执行结果如下:
2021-04-17:给定一个整型数组 arr,数组中的每个值都为正数,表示完成一幅画作需要的时间,再 给定 一个整数 num,表示画匠的数量,每个画匠只能画连在一起的画作。所有的画家 并行工作,请


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

展开阅读全文

© 著作权归作者所有

举报

打赏

0


0 收藏

微信
QQ
微博

分享

作者的其它热门文章

2021-04-14:判断二叉树是否是满二叉树?
2021-01-06:mysql中,我存十亿个手机号码,考虑存储空间和查询效率,用什么类型的字段去存?
2020-12-12:现场写代码,把CPU打满,java和go都行,并解释为什么。
2021-01-19:mysql中,一张表里有3亿数据,未分表,其中一个字段是企业类型,企业类型是一般企业和个体户,个体户的数据量差不多占50%,根据条件把个体户的行都删掉。请问如何操作?


喜欢 (0)