【题目描述】

 木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是事先给定的，切割时希望得到的小段越长越好。

      编写程序，输入原木的数目 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;  }

(adsbygoogle = window.adsbygoogle || []).push({});