MyPojId == zhaozhouyang

    非常经典的2分题目，要不是看discuss，怎么也想不到。

    题意：给你天数n，和每天需要花的钱，让你把这些天分成m份（每份都是连续的天），要求每份的和尽量少，输出这个和。

    一开始二分的上界为n天花费的总和（相当于分成1份），下界为每天花费的最大值（相当于分成n份），然后二分，每次的mid值为（上界 下界）/ 2，然后根据mid值遍历n天花费，对n天的花费进行累加，每当超过mid值份数 ，看看这个mid值能把n天分成几份，如果份数大于m，表示mid偏小，下界 = mid 1，反之小于等于mid，上界 = mid - 1，然后输出最后的mid值即可，复杂度为 O(nlogM)，M约为第一次的上界。

    代码如下：
#include <stdio.h>
int shu[1000002];
int n,m;
int divid(int mid)
{
int i;
int count=1,sum=0;
for(i=0;i<n;i )
{

   if(sum shu[i]<=mid)
    sum = sum shu[i];
   else
   { 
    count ;
    sum = shu[i];
   }
}
if(count>m)
   return 2;
else
   return 0;
}
int main()
{

int i,j;
int max,sum,k;
int mid,high,low;
while(scanf("%d%d",&n,&m)!=EOF)
{
   sum = 0;
   max = 0;
   for(i=0;i<n;i )
   {
    scanf("%d",&shu[i]);
    if(shu[i]>max)
     max = shu[i];
    sum = sum shu[i];
   } 
   low = max;
   high = sum;
   mid = (high low)/2;
   while(low<high)
   {
  
    k = divid(mid);
    //printf("%d %d %d\n",low,high,mid);
    if(k==2)
     low = mid 1;
    else
     high = mid-1;
    mid = (high low)/2;
   }
   printf("%d\n",mid);
}
return 0;
}