吃萝卜

时间限制: 1 Sec  内存限制: 128 MB

题目描述

在一个神奇的国度里,有一只编程兔,它每天都写很多的代码,各种编程语言如pascal、c、c++、java、basic等等它都了如指掌,各种算法也都已经滚瓜乱熟了。小花是它的好朋友,经常和它一起玩耍。
某一天,小花给编程兔送来了很多的萝卜。编程兔很开心,决定把它的萝卜和其它的小兔子一起分享。小花共计送来了n袋萝卜(编号1到n),每袋里面都有一定数量的萝卜。小兔子共计有m只,兔子们都很守规矩,按照编号1到m依次排好领取萝卜,萝卜按照编号从小到大的顺序依次发放(也就是编号小的兔子领取前面的萝卜,编号大的兔子领取后面的萝卜,萝卜一定要分完,不能有剩余),每只兔子都只能领取连续的若干袋萝卜,每只兔子至少领取一袋萝卜,一袋萝卜也只能分给一只兔子,不能分给两只以上的兔子。
编程兔希望萝卜尽量能分的平均一点(否则小兔子们要不开心的^_^),也就是它希望得到萝卜最多数量的兔子的萝卜要最少。这个问题对于编程兔来说很简单,亲爱的同学们,你们会么?

 

 

输入

第一行是两个正整数n和m,表示萝卜的袋数和兔子的数量。
第二行是n个正整数,表示每袋萝卜的数量。

 

输出

输出只有一行一个整数,表示得到萝卜最多的那只兔子最少可以得到的萝卜数量。

 

 

样例输入

复制样例数据

9 3
1 2 3 4 5 6 7 8 9

样例输出

17

 

提示

第1-5袋萝卜分给第一只兔子,总数是15个萝卜,第6-7袋萝卜分给第二只兔子,总数是13个萝卜,第8-9袋萝卜分给第三只兔子,总数是17个萝卜,萝卜最多的兔子得了17个萝卜,这是最多的兔子得到的最少的情况。如果第1-4袋分给第一只兔子,共计10个萝卜,第5-7袋分给第二只兔子共计18个萝卜,第8-9袋分给第三只兔子,共计17个萝卜,这样最多的兔子得到了18个萝卜,比之前的方案大,所以不是最优。

对于60%的数据,1<=m<=n<=100,每袋萝卜的数量不超过10。
对于100%的数据,1<=m<=n<=100000,每袋萝卜的数量不超过10000。

 

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, m;
int a[100005];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d %d", &n, &m);
	int l = 0, r = 0;
	for (int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		l = max(l, a[i]);
		r += a[i];
	}
	while(l <= r){
		int mid = (l + r) >> 1;
		int num = 0, sum = 0;
		for (int i = 1; i <= n; i++){
			sum += a[i];
			if(sum > mid){
				num++;
				sum = a[i];
			}
		}
		num++;
		if(num > m){
			l = mid + 1;
		}else{
			r = mid - 1;
		}
	}
	printf("%d\n", l);

	return 0;
}
/**/