#F. 月度开销

    Type: Default 1000ms 256MiB

月度开销

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。

约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案,他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天,每天被恰好包含在一个fajo月里。

约翰的目标是合理安排每个fajo月包含的天数,使得开销最多的fajo月的开销尽可能少。

【输入】

第一行包含两个整数N,M,用单个空格隔开。

接下来N行,每行包含一个1到10000之间的整数,按顺序给出接下来N天里每天的开销。

【输出】

一个整数,即最大月度开销的最小值。

【输入样例】

7 5
100
400
300
100
500
101
400

【输出样例】

500

【提示】

若约翰将前两天作为一个月,第三、四两天作为一个月,最后三天作为一个月,则最大月度开销为500。其他任何分配方案都会比这个值更大。

【来源】

一本通在线评测

20230318 二分法随堂测验

Not Attended
Status
Done
Rule
Ledo
Problem
6
Start at
2023-3-18 10:30
End at
2023-3-18 11:30
Duration
1 hour(s)
Host
Partic.
18