【装果子】

题目描述

果园里有 n 颗果树,每棵果树都有一个编号 i(1≤i≤n)。小明已经把每棵果树上的果子都摘下来堆在了这棵树的下方,每棵树下方的果子体积为 ai
现在小明将拿来 m 个袋子把这些果子都装进袋子里。每个袋子的体积为 v 。
小明会按照如下规则把果子装进袋子里:
(a) 从第 1 棵果树开始装起,由 1 到 n 一直装到第 n 棵果树。
(b) 如果这棵果树下的果子能全部装进当前这个袋子,就装进去;如果不能,就关上当前这个袋子,打开一个新的袋子开始装。
小明希望在能把所有果子都装进袋子里的前提下,v 尽量小。m 个袋子并不一定都要装进果子。

输入格式

输入第 1 行,包含两个整数 n 和 m 。
输入第 2 行,包含 n 个整数 a

输出格式

输出仅一行,表示最小的 v 。

样例数据 1

输入

3 3
1 2 3

输出

3

样例数据 2

输入

5 3
1 3 6 1 7

输出

7

样例数据 3

输入

6 3
1 2 1 3 1 4

输出

4

备注

【样例解释1】
每个袋子的体积为 3 即可。前 2 棵果树的果子装在第一个袋子里,第 3 棵果树的果子装在第二个袋子里。第三个袋子不用装了。

【样例解释2】
每个袋子的体积为 7 即可。前 2 棵果树的果子装在第一个袋子里,此时第一个袋子已经装了 4 单位体积的果子,第 3 棵果树的果子装不下了,所以装进第二个袋子里,第 4 棵果树的果子刚好装进第二个袋子,第 5 棵果树的果子装进第三个袋子里。

【样例解释3】
每个袋子的体积为 4 即可。前 3 棵果树的果子装在第一个袋子里,第 4~5 棵果树的果子装在第二个袋子里,第 6 棵果树的果子装在第三个袋子里。

【数据范围】
对于40%的数据,0<m≤n≤1,000,0<ai≤1,000;
对于70%的数据,0<m≤n≤100,000,0<ai≤100,000;
对于100%的数据,0<m≤n≤100,000,0<ai≤1,000,000,000。

很明显的二分答案,什么也不想说了二分正确,结果输出mid挂掉了,实际上是保存合法的mid再输出……二分答案的输出还是要多注意啊!

下面是代码:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*