B - C - Monthly Expense

二分

题目大意

给你n个数把他们连续的分成m组，问最小的那一组的最大值

解题思路

最大的那部分总和num存在一个范围，num总大于等于数组中最大的那个数，总小于等于整个数组的和。得到了一个范围a~b,用二分法不断缩小范围，比如第一次取mid = a + (a - b) / 2, 那么分组时候每组最大为mid，分到最后一个得到的组数如果小于等于m那就将范围缩小到a~mid,如果分得的组数大于m，那就将范围缩小到mid~b,直到不能缩小了就能得到最优值了

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int a[100010];
int fun(int a[],int mid)
{
    int sum=0,t=1;
    for(int i=1;i<=n;i++)
    {
        if(sum+a[i]<=mid)
            sum+=a[i];
        else
        {
            sum=a[i];
            t++;
        }
    }
    if(t>m)
        return 0;
    return 1;
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        int l,r=0;
        int mid,sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            if(a[i]>r)r=a[i];
        }
        l=sum;
        mid=(l+r)/2;
        while(r<l)
        {
            if(!fun(a,mid)) r=mid+1;
            else l=mid-1;
            mid=(r+l)/2;
        }
        printf("%d",mid);
    }
    return 0;
}