题意：按顺序给你N个数，将这N个数分成连续的M段，使得这M段每段的和中的最大值最小，输出最小值（1<=N<=100000,1<=M<=N,每个数在1到10000之间）。

思路：由于函数具有单调性的特征，因此可以用二分枚举的办法去实现它，这与POJ3258有非常相似的地方，但这里不需要排序。

 

CODE：

 

 

#include <cstdio>

#include <cstdlib>

#include <iostream>

using 

namespace std;

const 

int SIZE = 

100010;

int a[SIZE];

int low_bound, high_bound;

int n, m;

int BSearch(

int x, 

int y, 

int m)

{

    

int mid;

    

while(x <= y)

    {

        

int group = 

1, sum = 

0;

        mid = (x+y)>>

1;

        

for(

int i = 

1; i <= n; i++)

        {

            

if((sum+=a[i]) <= mid);

            

else

            {

                group++;

                sum = a[i];

            }

        }

        

if(group > m) x = mid+

1;

        

else y = mid-

1;

    }

    

return x;

}

int main()

{

    

while(~scanf(

"

%d%d

", &n, &m))

    {

        low_bound = -

1;

        high_bound = 

0;

        

for(

int i = 

1; i <= n; i++)

        {

            scanf(

"

%d

", &a[i]);

            low_bound = max(low_bound, a[i]);

            high_bound += a[i];

        }

        

int ans = BSearch(low_bound, high_bound, m);

        printf(

"

%d\n

", ans);

    }

    

return 

0;

}