记录编号	294207	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 月度花费	最终得分	100
用户昵称	浮生随想	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2016-08-11 19:14:53	内存使用	0.70 MiB

/*本来想做二分图的，结果一点没看出二分图来……反而是二分了……
很简单的思想，直接枚举一下可能的最大的清算月的钱数。
注意细节部分的调整*/ 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100010;
int n,m,a[maxn];
bool check(int x){
	int ans=0,cnt=0;
	for(int i=1;i<=n;i++){//区间查找，学的哒哒大神的代码。 
		cnt+=a[i];
		if(cnt+a[i+1]>x){//高能！！注意了！！
//在这里一定要判断加上下一个是不是超过了当前二分答案！
//如果直接用当前来计算，本来这个计划就已经超了，应该在上一个点就跳出。
//这个点应该加在下一个清算月中，但是cnt一清空，把这个点的值给抛弃了。 
			cnt=0;
			ans++;
		}
	}
	if(ans>=m)return 1;//如果当前这个答案超过了m个清算月的限制，那么很显然这个mid值太低了，应该往高了找。 
	else return 0;//反正，往低里去。 
}
int main(){
	freopen("expense.in","r",stdin);
	freopen("expense.out","w",stdout);
	int l=0,r=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		r+=a[i];
		l=max(l,a[i]);
	}
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	printf("%d",l);
}