学步园

题意：给你天数n，和每天需要花的钱，让你把这些天分成m份（每份都是连续的天），要求每份的和尽量少，输出这个和。

思路：二分

#include <iostream>
using namespace std;
#define maxn 100000
int day[maxn];
int n,m;
int  solve(int low,int high)
{
	if(low==high) return low;
	int mid=(low+high)/2;
	int temp=mid,c=0; 
	for(int i=0;i<n;++i)
	{
		if(temp-day[i]>=0) 
		{
			temp-=day[i];
		}
		else 
		{
			c++;
			temp=mid-day[i];
		}
	} 
	c++;
	if(c>m) return solve(mid+1,high);
	if(c<=m) return solve(low,mid-1);
}

int main()
{
 	int sum,max;
 	while(scanf("%d%d",&n,&m)!=EOF)
 	{
		sum=0;
		max=0;
		for(int i=0;i<n;++i) 
		{
			scanf("%d",&day[i]);
			sum+=day[i];
			if(day[i]>max) max=day[i];
		}
	     printf("%d\n",solve(max,sum));
    }
 	return 0;
}