鏈接:
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函數調用而已...而且由于這是查找最大解,返回值做了下變化而已...
仔細分析二分的寫法(我的另一篇文章(標題是關于密碼的一個解題報告)有說明),
其實寫出查找最大解和最小解的二分都不是件麻煩的事情...