POJ 3272 Monthly Expense 二分

题意：给你n个数，让分成m组，每组必须是连续的一些数，求每组的和的最大值最小。
思路：二分枚举答案。上界是n个数的和，也就是分成1组的情况，下界是n个数里面的最大值，也就是分成m组的情况，然后看mid = (rp + lp) / 2 能够把n个数分成多少组。其是就是二分枚举求下限的过程。
代码：
[cpp]
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;

typedef long long LL;
const int N = 100010;
int num[N];
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m) != EOF){
        LL value = 0;
        int mmax = 0;
       for(int i = 0; i < n; ++i){
           scanf("%d",&num[i]);
           if(mmax < num[i])
               mmax = num[i];
           value += num[i];
       }
       LL lp = mmax, rp = value,ans = 0;
       while(lp < rp){
          int cnt = 0;
          LL mmid = (lp + rp) / 2;
          LL sum = 0;
          for(int i = 0; i < n; ++i){
              sum += num[i];
              if(sum > mmid){
                cnt++;
                sum = num[i];
              }
          }
          if(cnt < m){
            rp = mmid;
          }
          else
              lp = mmid + 1;
       }
       printf("%lld\n",lp);
    }
    return 0;
}

补充：软件开发 , C++ ,