有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。
木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回 0 即可。
解释一下就是：给定了一个切割目标长度Len后，每一根原木都可以切割出多条，加在一起的数目totalCount要求大于等于k。在满足总数目totalCount大于等于k的条件下，得到一个最长的目标长度len。
暴力解
首先想到的是暴力解，当len给定，totalCount就可以计算出来，而且可以知道len越小，totalCount就越大。那么从最长的原木长度maxLen开始算总数，第一个满足totalCount>=k就是我们要的解。
时间复杂度是n*(maxLen-targetLen),随机情况来看，每个长度概率一样，就是n*(∑k/maxLen), 1<=k<=maxLen,即O(n*maxLen)。
这个肯定是不够的。
动态规划
对于最有解的问题，很自然的会想到动态规划，而动态规划的核心的找到大问题向小问题的转移方式。在这一题里，也就是找到切割目标长度len时的总数和len+1时的总数之间的关系，倘若这两者直接的计算复杂度为O(x),那么总复杂度为O(x*maxLen),那么只要x<n就可以得到优化。
有什么办法可以让两个总长度直接关联得到计算，而不需要再次循环一个个原木从新计算呢？这个我尝试了，没想出来。
二分法
然后看了眼题目的标签，是二分法，瞬间感觉有戏了。
这个情况里最有用的一个分析是：目标长度len越小，总数totalCount就越大。对比一个二分查抄的逻辑，找到一个目标来分隔区间，然后不断的缩小区间，最后剩下的是解。这里就是：一开始的选择区间是[1,maxLen],取中数mid，求出总数,和k比较，如果总数小，那么就要继续压小长度，那么选择区间就变成了[1,mid]，反之选择区间就是[mid,maxLen]。按照这样的思路，区间不断缩小，最后找到解。
int woodCut(vector<int> &L, int k) {
int maxLen = 0;
int residue = k;
for (int len : L){
if (residue>0) {
residue -=len; //不直接比较总量是因为可能会超出int范围
}
maxLen = max(maxLen, len);
}
//排除头<k
if (residue > 0) {
return 0;
}
//排除尾>=k
int maxLenCount = 0;
for (int len : L){
if (len == maxLen) {
if ((++maxLenCount)==k) {
return maxLen;
}
}
}
//循环不变条件是：左边结果>=k,右边<k。所以前面先把不满足的头和尾情况排除,逼近到最后left和right相邻时，left就是解。
int left = 1, right = maxLen;
while (left < right-1) {
int mid = left+(right-left)/2;
int count = 0;
for (int len : L){
count += len/mid;
}
if (count<k) {
right = mid;
}else{
left = mid;
}
}
return left;
}
启示
这题给我最大的一个启示是:二分法的使用跟环境存在一个单调递增或递减的关系是紧密相关的。
假设存在两个变量A和B,A和B的关系是单调递增或递减，假设为递增，即A月大则B越大。然后我们要求B为b'时的A的值a'，那么就可以用二分法了。
先来一个区间[a1, a2]，只要a1和a2对应的B值是在目标的两边，即一个大于目标一个小于目标，那么就可以用二分法的手段不断的压缩区间直到最后找到解。
那如果a1,a2对应的B值在同一边呢？那么一般这种情况下， 已经到了边缘还没有解，就是求最近的数，那么解就是a1或者a2。
解算法题，找到对应的解法模型问题就会很快，那怎么知道某一题对应了什么样的解法模型，我觉得就是有一些引子、征兆之类的东西，这才是我想说的，这个切木头题目只是个例子。对于二分法，它的一个征兆就是存在两个变量，它们之间有单调递减或递增的关系。
网友评论