【题目描述】

 木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是事先给定的，切割时希望得到的小段越长越好。
      编写程序，输入原木的数目 N 和需要得到的小段的数目 K以及各段原木的长度，计算能够得到的小段木头的最大长度。
      木头长度的单位是 cm。原木的长度都是正整数，要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为11和21，要求切割成到等长的6段，很明显能切割出来的小段木头长度最长为5.

【输入描述】

第一行是两个正整数N和K(1 ≤ N ≤ 100000，1 ≤ K ≤ 100000000)，N是原木的数目，K是需要得到的小段的数目。

接下来的N行，每行有一个1到100000000之间的正整数，表示一根原木的长度。

【输出描述】

能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。

【样例输入】

3 7
232
124
456

【样例输出】

114

注: 请对比  切割钢管 这道题目

【题目分析】

采用二分法进行解决（最大化平均值问题）。
      设left是切割的小段木头的最短长度，right是最大长度，初始时，left为0，right为最长的原木长度加1。
      每次取left和right的中间值mid（mid = (left + right) / 2）进行尝试，测试采用当前长度mid进行加工，能否切割出需要的段数K，测试算法描述为：

   num = 0;
      for (i = 0; i < n; i++)
      {
            if (num >= k) break;
            num = num + len[i] / mid ;
      }

    如果当前mid值可以加工出所需段数（即num >= k），说明当前mid值偏小，可能有余量，就增大mid值继续试（通过让left = mid的方法来增大mid）；不符合要求，当前mid值加工不出所需段数，显然mid偏大了，就减小mid值继续试（通过让right = mid的方法来减小mid）。直到left +1>= right结束尝试，所得的left值就是可以加工出的小段木头的最大长度。

【参考代码】

#include <iostream>
using namespace std;
int main()
{
      int n, k, len[10000], i, left, right, mid,num;
      cout<<"请输入原木的数目 N 和需要得到的小段的数目 K ："<<endl;
      cin>>n>>k;
      right = 0;
      cout<<"请输入各段原木的长度："<<endl;
      for (i = 0; i < n; i++)
      {
            cin>>len[i];
            if (right < len[i]) right = len[i];
      }
      right++;
      left = 0 ;
      while ( left + 1 < right)
      {
            mid = (left + right) / 2;
            num = 0;
            for (i = 0; i < n; i++)
            {
                  if (num >= k) break;
                  num = num + len[i] / mid ;
            }
            if ( num >= k )
                  left = mid;
            else
                  right = mid;
       }
      cout<<"能够切割得到的小段的最大长度为 "<<left<<endl;
      return 0;
}