首页 > 试题广场 >

最优分割

[编程题]最优分割
  • 热度指数:2798 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
依次给出n个正整数A1,A2,… ,An,将这n个数分割成m段,每一段内的所有数的和记为这一段的权重, m段权重的最大值记为本次分割的权重。问所有分割方案中分割权重的最小值是多少?

输入描述:
第一行依次给出正整数n,m,单空格切分;(n <= 10000, m <= 10000, m <= n)
第二行依次给出n个正整数单空格切分A1,A2,… ,An (Ai <= 10000)


输出描述:
分割权重的最小值
示例1

输入

5 3
1 4 2 3 5

输出

5

说明

分割成 1  4 |   2   3  |   5  的时候,3段的权重都是5,得到分割权重的最小值。
头像 牛客题解官
发表于 2020-06-05 16:05:23
题解 题目难度:中等难度 知识点:二分法、查找、数组 首先考虑:这是一道查找题,可确定最小值的范围,再使用方法逐渐逼近这个最优解。 二分法逼近最小值 首先明确这个最小值一定是介于(max(nums),sum(nums))之间,因此我们可以使用二分查找来缩小范围。第一步:先确定个mid=(sum+ma 展开全文