poj-3273-Monthly Expense-二分

题意：

给你n m

然后给你n个数。让你把这n个数分为m个部分，每个部分都是连续的。问所有部分中的最大值最小的值。

做法：

二分。一开始上届是n个数的和。代表只分一组。

下届是n个数中最大的数。代表分n组；

如果结果是mid=（上届+下届）/2；那么根据mid看看能分多少组。组数大于m，代表mid比实际值小。下届变成mid+1。否则，上届变成mid-1；

#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)    {        if(sw(mid))l=mid+1;        else r=mid-1;        mid=(l+r)/2;    }    cout<<mid<<endl;    return 0;}