A8027.数列分段

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

对于给定的一个长度为N的正整数数列 A1NA_{1\sim N},现要将其分成 MMMNM\leq N)段,并要求每段连续,且每段和的最大值最小。

关于最大值最小:

例如一数列 4 2 4 5 14\ 2\ 4\ 5\ 1 要分成 33 段。

将其如下分段:

[4 2][4 5][1][4\ 2][4\ 5][1]

第一段和为 66,第 22 段和为 99,第 33 段和为 11,和最大值为 99

将其如下分段:

[4][2 4][5 1][4][2\ 4][5\ 1]

第一段和为 44,第 22 段和为 66,第 33 段和为 66,和最大值为 66

并且无论如何分段,最大值不会小于 66

所以可以得到要将数列 4 2 4 5 14\ 2\ 4\ 5\ 1 要分成 33 段,每段和的最大值最小为 66

输入格式

11 行包含两个正整数 N,MN,M

22 行包含 NN 个空格隔开的非负整数 AiA_i,含义如题目所述。

输出格式

一个正整数,即每段和最大值最小为多少。

输入输出样例

  • 输入#1

    5 3
    4 2 4 5 1

    输出#1

    6

说明/提示

对于 20%20\% 的数据,N10N\leq 10

对于 40%40\% 的数据,N1000N\leq 1000

对于 100%100\% 的数据,1N1051\leq N\leq 10^5MNM\leq NAi<108A_i < 10^8, 答案不超过 10910^9

【普及组算法7】二分查找与二分答案

0/10
首页