最优分割

[编程题]最优分割

热度指数：2783 时间限制：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

输出

说明

分割成 1  4 |   2   3  |   5  的时候，3段的权重都是5，得到分割权重的最小值。

算法知识视频讲解

牛客题解官

发表于 2020-06-05 16:05:23

题解题目难度：中等难度知识点：二分法、查找、数组首先考虑：这是一道查找题，可确定最小值的范围，再使用方法逐渐逼近这个最优解。二分法逼近最小值首先明确这个最小值一定是介于（max(nums),sum(nums))之间，因此我们可以使用二分查找来缩小范围。第一步：先确定个mid=（sum+ma 展开全文