poj-3273-Monthly Expense-二分

题意：
给你n m
然后给你n个数。让你把这n个数分为m个部分，每个部分都是连续的。问所有部分中的最大值最小的值。
做法：
二分。一开始上届是n个数的和。代表只分一组。
下届是n个数中最大的数。代表分n组；
如果结果是mid=（上届+下届）/2；那么根据mid看看能分多少组。组数大于m，代表mid比实际值小。下届变成mid+1。否则，上届变成mid-1；
 
[html] 
#include<iostream>  
#include<stdio.h>  
#include<string.h>  
using namespace std;  
int a[100100];  
int n,m;  
int sw(int mid)  
{  
    int s,num,i;  
    s=0;  
    num=1;  
    for(i=0;i<n;i++)  
    {  
        if(s+a[i]<=mid)  
        {  
            s+=a[i];  
        }  
        else  
        {  
            s=a[i];  
            num++;  
        }  
    }  
    if(num>m)return 1;  
    else return 0;  
}  
int main()  
{  
    int l,r,i,mid;  
    cin>>n>>m;  
    r=0;  
    l=0;  
    for(i=0;i<n;i++)  
    {  
        scanf("%d",&a[i]);  
        r+=a[i];  
        if(a[i]>l)l=a[i];  
    }  
    mid=(l+r)/2;  
    while(l<r)  
    {    www.zzzyk.com
        if(sw(mid))l=mid+1;  
        else r=mid-1;  
        mid=(l+r)/2;  
    }  
    cout<<mid<<endl;  
    return 0;  
  
}

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