codevs 1766 装果子

题目描述 Description

果园里有n颗果树，每棵果树都有一个编号i(1≤i≤n)。小明已经把每棵果树上的果子都摘下来堆在了这棵树的下方，每棵树下方的果子体积为a_i。

现在小明将拿来m个袋子把这些果子都装进袋子里。每个袋子的体积为v。小明会按照如下规则把果子装进袋子里：
(a)从第1棵果树开始装起，由1到n一直装到第n棵果树。
(b)如果这棵果树下的果子能全部装进当前这个袋子，就装进去；如果不能，就关上当前这个袋子，打开一个新的袋子开始装。
小明希望在能把所有果子都装进袋子里的前提下，v尽量小。m个袋子并不一定都要装进果子。

输入描述 Input Description

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

输出描述 Output Description

输出仅1行，表示最小的v。

样例输入 Sample Input

#1
3 3
1 2 3
#2
5 3
1 3 6 1 7
#3
6 3
1 2 1 3 1 4

样例输出 Sample Output

#1
3
#2
7
#3
4

数据范围及提示 Data Size & Hint

【输入输出样例解释1】

每个袋子的体积为3即可。前2棵果树的果子装在第一个袋子里，第3棵果树的果子装在第二个袋子里。第三个袋子不用装了。

【输入输出样例解释2】

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

【输入输出样例解释3】

每个袋子的体积为4即可。前3棵果树的果子装在第一个袋子里，第4~5棵果树的果子装在第二个袋子里，第6棵果树的果子装在第三个袋子里。

【数据范围】

对于40%的数据，0<m≤n≤1,000，0<a_i≤1,000；
对于70%的数据，0<m≤n≤100,000，0<a_i≤100,000；
对于100%的数据，0<m≤n≤100,000，0<a_i≤1,000,000,000。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll num[2332332];
int main()
{
	ll n, m;
	cin>>n>>m;
	for(ll i = 1;i <= n;i ++)
	{
		scanf("%I64d", &num[i]);
	}
	ll l = 1, r = 1e15, mm;
	while(r-l>(ll)1)
	{
		mm = (ll)1;
		bool flag = 0;
		ll mid = (l + r)/(ll)2;
		ll v = mid;
		for(ll i = 1;i <= n;i ++)
		{
			if(num[i] > mid)
			{
				l = mid;
				flag = 1;
				break;
			}
			if(v - num[i] < 0)
			{
				v = mid - num[i];
				mm++;
			}
			else
			{
				v -= num[i];
			}
		}
		if(flag == 1)
			continue;
		if(mm > m)
			l = mid;
		else
			r = mid;
	}
	cout<<r;
	return 0;
}