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; 
}