网站分类表,佛山顺德容桂做网站的公司,wordpress 登录框,微商手机网站制作这是二分法的第20篇算法#xff0c;力扣链接。 给定一个非负整数数组 nums 和一个整数 k #xff0c;你需要将这个数组分成 k 个非空的连续子数组。 设计一个算法使得这 k 个子数组各自和的最大值最小。 示例 1#xff1a; 输入#xff1a;nums [7,2,5,10,8], k 2
输出力扣链接。 给定一个非负整数数组 nums 和一个整数 k 你需要将这个数组分成 k 个非空的连续子数组。 设计一个算法使得这 k 个子数组各自和的最大值最小。 示例 1 输入nums [7,2,5,10,8], k 2
输出18
解释
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18在所有情况中最小。 示例 2 输入nums [1,2,3,4,5], k 2
输出9 这道题先不暴力了暴力一点都不好玩我们可以试试二分法解决问题。
使得..最大值最小是标准二分法的套路背下来要考的。
但是二分法要求得是个有序的序列啊这个什么是有序的呢和是有序的。我们可以让右边界为整个数组的和左指针为数组的最小值。
那左右移动的临界条件怎么判断呢我们可以利用贪心的逻辑去判断。
设已经累加的值为sum切的刀为cnt每当sum num mid 的时候就去追加一刀重新开始当刀数不够就左指针右移刀数正好或者富裕就右指针左移。
func splitArray(nums []int, k int) int {l, r : 0, 0for _, num : range nums {r numif l num {l num}}for l r {mid : l (r-l)/2if checkCount(nums, mid, k) {r mid - 1} else {l mid 1}}return l
}func checkCount(nums []int, mid int, k int) bool {sum, cnt : 0, 1for _, num : range nums {if sumnum mid {cntsum num} else {sum num}}return cnt k
}当然这道题也适合动态规划在后续动态规划的篇章再来重温。
