POJ3273Monthly Expense（二分）

http://poj.org/problem?id=3273

题意： 农夫约翰给出了n天的每天花费 ，让你将这n天分成m组，每组中存在的天数必须是连续的，然后让每组里花费的总和尽量的小，最后将花费最大的那个费用输出 。

思路 ：分在数学计算方法里的这4个题好像都是二分吧，这个题也是用的二分。

#include<cstdio>
#include<iostream>
using namespace std ;
int a[110000] ;
int main()
{
    int n ,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        int low = 0,high = 0 ,sum = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            scanf("%d",&a[i]) ;
            low = max(low,a[i]) ;//让这些钱数中的最大值做为下界，这样的话，所求的值必然在最大值和总和之间
            high += a[i] ;
        }
        int mid ;
        while(low <= high)
        {
            mid =  (low+high)/2 ;
            sum = 0 ;
            int cnt = 0 ;
            for(int i = 1 ; i <= n ; i++)
            {
                sum += a[i] ;
                if(sum > mid)//如果前几天的钱的总数大于mid，则把前i-1天作为一组，而且分组数加1.
                {
                    cnt++ ;
                    sum = a[i] ;
                }
            }
            if(sum != 0)//最后一个分组
                cnt++ ;
            if(cnt > m)//如果分组比m多说明，分的钱数太少了，需要增加下界
                low = mid+1 ;
            else high = mid-1 ;
        }
        printf("%d
",mid) ;
    }
    return 0 ;
}