木材加工问题
【问题描述】
木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目是给定了。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。
木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是正整数。
【输入描述】
第一行是两个正整数N和K(1 ≤ N ≤ 10000, 1 ≤ K ≤ 10000)，N是原木的数目，K是需要得到的小段的数目。
接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。
【输出描述】
输出能够切割得到的小段的最大长度。如果连1厘米长的小段都切不出来，输出”0″。
【样例输入1】
3 7
232
124
456
【样例输出1】
114
【样例输入2】
3 8
124
224
319
【样例输出2】
74
【分析】
以样例1为例
加入我以100为单位去切232、124、456这三块木头，能切成2+1+4=7，按照题目要求能切成7段，但是不是最优解，因为题目要求得到的段越长越好，而101也符合要求，而且比100切出的段更长，那么实际上这道题就是在求题目要求的最优解。
那么这道题目可以考虑使用二分法来求解。
有人问我可不可以用暴力穷举法，每种长度都试试，这样能得出结论但是在竞赛中大概率会超时。
我们假设left是切割小段的最短长度，left初始值为0，right是切割小段的最大长度，right的初始值为所有木材当中最长的那个。
可以看出，实际上我们
那么像这样的题用二分法有什么好处呢？
可以看出，上面的程序中，我们每次用mid值去且木头，
①第一次的值是1+1+1+1=4<7 ,没有达到目标值，说明mid值取的大了。应该取小点，所以修改右区间端点的值。
②第二次的是是2+1+1+2+1=7，mid取值切割后符合目标值，这里已经出现符号目标值的mid值，那为什么还要取第三次呢？这就是文章一开始讲的，mid值为100和101的时候都能切出7块，但显然101比100更优，因为题目中要求切出的块尽量大。
③第三次的值是2+1+1+1+1=6<7。说明mid值有点大，要继续划分区间。
④ …….
那么，上面这个过程需要我们至少要做两件事，第一就是结束条件，第二个就是切割木头符合时的判断。
num = 0;
for (i = 0; i < n; i++)
{
if (num >= k) break;
num = num + len[i] / mid ;
}
这里的num可以表示最终切的段数，mid表示每次取的中值。
#include <iostream>
using namespace std;
int main()
{
int n, k, len[10000], i, left, right, mid,num;
cin>>n>>k; //读入木头数量和最小需要得到的小段数目
right = 0;
for (i = 0; i < n; i++)
{
cin>>len[i];
if (right < len[i]) right = len[i]; //用right取得最大长度。
}
right++; //从0开始的，此处要++
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 ) //如果切的数量比k多
left = mid;
else
right = mid;
}
cout<<left<<endl;
return 0;
}
除此之外，我们也可以写成函数形式。用一个函数来判断能否切割成合适的块数。
int f(int mid)
{
if(mid==0) return false;
int sum=0;
for(int i=1;i<=n;i++)
sum+=a[i]/mid;
if(sum>=m) //切的块数大于等于给定的块数
return true;
return false;
}
然后，在主函数中调用即可。
#include <iostream>
using namespace std;
int n,m;
int a[100010],l,r=0,mid,maxn=0; //maxn表示最终能切的的木段的最大长度
int f(int mid) {
if(mid==0) return false;
int sum=0;
for(int i=1; i<=n; i++)
sum+=a[i]/mid;
if(sum>=m)
return true;
return false;
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>a[i];
r=max(r,a[i]);//用max 取得最大值
}
l=1; //从1开始录入的
while(l<=r) {
mid=(l+r)/2;
if(f(mid)) {
maxn=max(maxn,mid);
l=mid+1;
} else
r=mid-1;
}
cout<<maxn;
return 0;
}
上面两个代码都借鉴了二分法的思想，不断缩小左右端点值，直到左右端点相遇为止。由于题目中给定的条件是 所有单位都是整数，那么左区间端点值和右区间端点值最多只差1。
后记
另外一些题目中，最后切的的单位不一定是整数，这个时候就需要在结束条件这个地方进行修改了。后面几篇博客中，会详细描述这种情况。
返回目录：算法