小明的花费预算
Time Limit: 1000ms Memory limit: 65536K

题目描述
小明终于找到一份工作了，但是老板是个比较奇怪的人，他并不是按照每月每月的这样发工资，他觉得你想什么时候来取都可以，取的是前边连续几个月中没有取的工资，而小明恰好是一个花钱比较大手大脚的人，所以他希望每次取得钱正好够接下来的n个月的花费。
所以让你把这n个月分成正好m组。每个组至少包含一个月，每组之中的月份必须是连续的，请你为他分组，使得分得的组中最大的总花费最小。

输入
第一行是两个整数，n（1 ≤ n ≤ 100,000)和m (1 ≤ m ≤ n)
接下来的n行是连续n个月的花费，第i+1行是第i个月的花费。

输出
输出满足最大的总花费最小的那个组的总花费。

示例输入
5 3
3
2
9
4
1

示例输出
9

提示
将5个月分为3组，第一组(3,2),第二组(9),第三组(4,1)，第二组的总花费最大为9，若按其他的方式分，花费最大的那一组的总花费将>=9.

来源
lwn

#include <iostream>
#include<bits/stdc++.h>
#define oo 50010
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
    int n,m;
    int a[100010];
    while(~scanf("%d%d",&n,&m))
    {

        int low = 0,high =0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            low = max(a[i],low);
            high += a[i];
        }
        int mid,ans;
        while(low<=high)
        {
            mid = (low+high)/2;
            int sum =0,num=1;
            for(int i=0;i<n;i++)
            {
                if(sum+a[i]<=mid)
                {
                    sum+=a[i];
                }
                else
                {
                num++;
                sum = a[i];
                }
            }
            if(num<=m)
            {
            high = mid-1;
           ans = mid;  //当符合题意时更新答案
            }
            else
            {
                low = mid+1;
            }

        }
        cout<<mid<<endl;
    }
}

运用二分来找最小的最大总花费mid，当sum不大于mid时，这些数据归为一组，当sum大于mid时，num++表示另加一组，当总的组数num<m时，说明组数少，意味着mid偏大，反之，同理


  1. 这道题的思想是二分答案，即先确定答案的范围，然后在范围内通过不断二分来确定答案。 <br>  
  2. 首先根据题意，我们根据分得的所有组中的最大花费来确定二分的范围 [low, high]，最小的情况 low 是花费最大的一个月自成一组，而最大的情况 high 是所有月全部构成一组。确定好二分范围后，每次我们二分时，都取中间值 mid 作为假设的答案，即分得的所有组中的最大花费，然后遍历一遍数组，以 mid 为花费上限<strong>尽可能少地分组</strong>，并根据分得的组数 cnt 来进行下一步判断：</p>  
  3. <p>如果 cnt > m，说明以 mid 作为最大花费分得的组数过多，mid 太小，不是合法答案，故要到右半边继续二分；</p>  
  4. <p>如果 cnt <= m，说明以 mid 作为最大花费分得的组数正好或偏少，由于我们是按照花费不大于 mid 且使组数尽可能少的原则分组（不够 m 的话可以通过拆分某些组来使组数达到 m），故 cnt <= m 的情况是合法答案，更新最终结果 ans = min(mid ,ans) 并向左半边继续二分（由于向左二分，每次得到的合法答案都必然比上一次的小，因此我们也可以直接写成 ans = mid）。