首页分享木材加工最优切割策略探讨

木材加工最优切割策略探讨

来源：花匠小妙招时间：2024-12-18 14:57

题目：B:木材加工总时间限制: 1000ms 内存限制: 65536kB 描述木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目是给定了。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是正整数。输入第一行是两个正整数N和K(1 ≤ N ≤ 10000, 1 ≤ K ≤ 10000)，N是原木的数目，K是需要得到的小段的数目。接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。输出输出能够切割得到的小段的最大长度。如果连1厘米长的小段都切不出来，输出"0"。样例输入 3 7 232 124 456 样例输出 114

解题思路：将所有原木从小到大排列，分别按它们的长度作为小段木头长度（所以小段木头长度会是增加的，得到的小段木头数也会减少的），直到得到的小段木头数比k要小（若一开始就比k小，则小段木头长度从第一个原木长度往下减），这样得到了此时对应的原木长度，在该长度基础上，往下每次减一，直到找到第一个长度，使得小段木头数大于等于K，这就是最大小段木头长度（或者减到末尾为0的边界情况，就赋值成0）。

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

int n, k, length, no, num;

cin >> n >> k;

int a[n];

for(int i = 0; i < n; i++)

cin >> a[i];

sort(a, a + n);

for(int i = 0; i < n; i++)

{

length = a[i];

no = i;

num = 0;

for(int j = 0; j < n; j++)

num += a[j]/length;

if(num < k)

{

break;

}

if(no == n - 1)

{

num = 0;

for(int j = 0; j < n; j++)

num += a[j]/length;

if(num >= k)

{

cout << length <<endl;

return 0;

}

for(length = a[no] - 1; length > 0; length--)

{

num = 0;

for(int j = 0; j < n; j++)

num += a[j]/length;

if(num >= k)

break;

}

if(length < 0)

length = 0;

cout << length <<endl;

system("pause");

return 0;

}

上面的方法超时了，而下面的暴力穷举方法（数值不大，所以可以这么做！）居然通过了，估计是（1）多花时间在第一个for循环了，而第二个for循环也没有减少很多情况，这很可能也是测试用例的问题，使得上面的方法两个for循环都执行很久才跳出来；（2）sort函数给a数组排序耗时很多。不过平均情况，上面的方法思想是更好的！

#include<iostream>

using namespace std;

int main()

{

int n, k, length, num;

cin >> n >> k;

int a[n];

for(int i = 0; i < n; i++)

cin >> a[i];

for(length = 10000; length > 0; length--)

{

num = 0;

for(int j = 0; j < n; j++)

num += a[j]/length;

if(num >= k)

break;

}

cout << length <<endl;

system("pause");

return 0;

}

我看了下NOIP2004年的答案，估计排序耗时很多，所以没有用第一种方法，而是在我暴力穷举法上优化了很多，主要分为两点（1）一边输入一边判断来找到木材原长最大的值，记为max，作为for循环的起始值，而不是10000；（2）每次折半查找，即length变为max/2，若此时的length仍不能使得小段木头数大于等于K，则length变为(1/4)*max，否则，length变为(3/4)*max，如此折半查找下去，直到找到结果或边界情况。