2774:木材加工
时间限制: 1000ms内存限制: 65536kB描述木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目是给定了。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是正整数。
输入
第一行是两个正整数N和K(1 ≤ N ≤ 10000, 1 ≤ K ≤ 10000)，N是原木的数目，K是需要得到的小段的数目。
接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。
输出输出能够切割得到的小段的最大长度。如果连1厘米长的小段都切不出来，输出"0"。样例输入3 7232124456样例输出114 链接: http://poj.grids.cn/practice/2774
这个题可以用二分解,虽然也有dp的解法。可能用二分解这个题不是很明显,但是确实是可以的。最大的解就是所有的棍子长/要求的棍子数,最小的解是0,直接在其中进行二分即可。这个题属于二分出最大满足条件的解的情况。这个题为什么能够二分了。我是这样想的。首先,解空间确实是有序的吧,从数字0-数字nSum/nK。其次,对于任意一个处于这个范围内的数字,只有满足和满足题目要求2种情况,那么和我们二分数字有什么区别了,我们二分一个有序数组,看里面有没有某个数字,是不是也只要判断下nMid满足是否条件是吧。所以,这个题是可以二分的。二分的条件就是解空间有序的,或者可以方便在解空间里面跳跃。而且这个题的二分还需要点技巧,因为是查找满足条件的最大解。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX (10000 + 10)
using namespace std;
int nN, nK;
int nWoods;
bool IsAnsOk(int nAns)
{
if (nAns == 0)
{
return true;
}
else
{
int nTotal = 0;
for (int i = nN - 1; i >= 0; --i)
{
nTotal += nWoods / nAns;
if (nTotal >= nK)
{
return true;
}
}
return false;
}
}
int SearchAns(int nMax)
{
int nBeg = 0, nEnd = nMax;
while (nBeg <= nEnd)
{
int nMid = (nBeg + nEnd) / 2;
if (IsAnsOk(nMid))
{
nBeg = nMid + 1;
}
else
{
nEnd = nMid - 1;
}
}
return nBeg - 1;
}
int main()
{
while (scanf("%d%d", &nN, &nK) == 2)
{
int nSum = 0;
for (int i = 0; i < nN; ++i)
{
scanf("%d", &nWoods);
nSum += nWoods;
}
sort(nWoods, nWoods + nN);
int nMax = nSum / nK;
printf("%d\n", SearchAns(nMax));
}
return 0;
}
所以,只是把==换成了IsAnsOk函数调用而已...而且由于这是查找最大解,返回值做了下变化而已...
仔细分析二分的写法(我的另一篇文章(标题是关于密码的一个解题报告)有说明),
其实写出查找最大解和最小解的二分都不是件麻烦的事情...
页:
[1]