2774:木材加工

winston

时间限制: 1000ms内存限制: 65536kB描述木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目是给定了。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。

木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是正整数。
输入
第一行是两个正整数N和K(1 ≤ N ≤ 10000, 1 ≤ K ≤ 10000)，N是原木的数目，K是需要得到的小段的数目。
接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。
　输出输出能够切割得到的小段的最大长度。如果连1厘米长的小段都切不出来，输出"0"。样例输入3 7232124456样例输出114

winston

链接: http://poj.grids.cn/practice/2774

这个题可以用二分解,虽然也有dp的解法。可能用二分解这个题不是很明显,但是确实是可以的。最大的解就是所有的棍子长/要求的棍子数,最小的解是0,直接在其中进行二分即可。这个题属于二分出最大满足条件的解的情况。这个题为什么能够二分了。我是这样想的。首先,解空间确实是有序的吧,从数字0-数字nSum/nK。其次,对于任意一个处于这个范围内的数字,只有满足和满足题目要求2种情况,那么和我们二分数字有什么区别了,我们二分一个有序数组,看里面有没有某个数字,是不是也只要判断下nMid满足是否条件是吧。所以,这个题是可以二分的。二分的条件就是解空间有序的,或者可以方便在解空间里面跳跃。而且这个题的二分还需要点技巧,因为是查找满足条件的最大解。

代码:

4. #include <stdio.h>
5. #include <string.h>
6. #include <algorithm>
7. #define MAX (10000 + 10)
8. using namespace std;
10. int nN, nK;
11. int nWoods[MAX];
12. bool IsAnsOk(int nAns)
13. {
14.     if (nAns == 0)
15.     {
16.         return true;
17.     }
18.     else
19.     {
20.         int nTotal = 0;
21.         for (int i = nN - 1; i >= 0; --i)
22.         {
23.             nTotal += nWoods[i] / nAns;
24.             if (nTotal >= nK)
25.             {
26.                 return true;
27.             }
28.         }
29.         return false;
30.     }
31. }
33. int SearchAns(int nMax)
34. {
35.     int nBeg = 0, nEnd = nMax;
37.     while (nBeg <= nEnd)
38.     {
39.         int nMid = (nBeg + nEnd) / 2;
40.         if (IsAnsOk(nMid))
41.         {
42.             nBeg = nMid + 1;
43.         }
44.         else
45.         {
46.             nEnd = nMid - 1;
47.         }
48.     }
50.     return nBeg - 1;
51. }
53. int main()
54. {
55.     while (scanf("%d%d", &nN, &nK) == 2)
56.     {
57.         int nSum = 0;
58.         for (int i = 0; i < nN; ++i)
59.         {
60.             scanf("%d", &nWoods[i]);
61.             nSum += nWoods[i];
62.         }
63.         sort(nWoods, nWoods + nN);
64.         int nMax = nSum / nK;
65.         printf("%d\n", SearchAns(nMax));
66.     }
68.     return 0;
69. }

复制代码

所以,只是把==换成了IsAnsOk函数调用而已...而且由于这是查找最大解,返回值做了下变化而已...
仔细分析二分的写法(我的另一篇文章(标题是关于密码的一个解题报告)有说明),
其实写出查找最大解和最小解的二分都不是件麻烦的事情...