链接:
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[MAX];
bool IsAnsOk(int nAns)
{
if (nAns == 0)
{
return true;
}
else
{
int nTotal = 0;
for (int i = nN - 1; i >= 0; --i)
{
nTotal += nWoods[i] / 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[i]);
nSum += nWoods[i];
}
sort(nWoods, nWoods + nN);
int nMax = nSum / nK;
printf("%d\n", SearchAns(nMax));
}
return 0;
}
所以,只是把==换成了IsAnsOk函数调用而已...而且由于这是查找最大解,返回值做了下变化而已...
仔细分析二分的写法(我的另一篇文章(标题是关于密码的一个解题报告)有说明),
其实写出查找最大解和最小解的二分都不是件麻烦的事情...