当前位置:首页 > 题解目录 > 正文内容

【题解】木材加工

亿万年的星光3年前 (2022-03-19)题解目录2241

【题目描述】

 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头(木头有可能有剩余),需要得到的小段的数目是事先给定的,切割时希望得到的小段越长越好。
      编写程序,输入原木的数目 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;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

标签: 二分
分享给朋友:

相关文章

【题解】合并有序表

【题目描述】k路归并问题把k个有序表合并成一个有序表。元素共有n个。【输入描述】读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数,表示第i个序列。总数小于100000。【输出描述】输...

【题解】最大配对

题目描述      给出2个序列A={a[1],a[2],…,a[n]},B={b[1],b[2],…,b[n]},从A、B中各选出n个元素进行一一配对(可以不按照原来在...

【题解】上学线路(2019青岛市程序设计比赛)

【题解】上学线路(2019青岛市程序设计比赛)

 【题目描述】小D从家到学校的道路结构是这样的:由n条东西走向和m条南北走向的道路构成了一个n*m的网格,每条道路都是单向通行的(只能从北向南,从西向东走)。已知小D的家在网格的左上角,学校...

【题解】大整数加法

【题目描述】求两个不超过200位的非负整数的和。【输入】有两行,每行是一个不超过200位的非负整数,可能有多余的前导0。【输出】一行,即相加后的结果。结果里不能有多余的前导0,即如果结果是342,那么...

【题解】吃糖果

【题解】吃糖果

【题目描述】小明终于从小红手里赢走了所有的糖果,小明转变吃掉所有糖果,但是小明吃糖果有个特殊癖好,就是不喜欢将一样的糖果放在一起吃,喜欢先吃一种,下一次吃另外一种。试问小明是否存在一种吃糖果的顺序使得...

【题解】老王赛马

【题目描述】赛马是一古老的游戏,早在公元前四世纪的中国,处在诸侯割据的状态,历史上称为“战国时期”。在魏国作官的孙膑,因为受到同僚庞涓的迫害,被齐国使臣救出后,到达齐国国都。 赛马是当时最受...