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