问题如图：
讯享网
注：木头不一定都要用，用也不一定都要用完
- 问题可以转化成在1和给的所有原木中最长的长度中间找一个合适的长度，使得把每段原木按此分段后得到的小段木头数目至少为k：在1—max之间用折半查找，找到最大的长度
//def woodCut(self, L, k){
// if sum(L) < k : // return 0 // // start, end = 1, max(L) // while start + 1 < end : // mid = start + (end - start) / 2 // pieces = sum([l / mid for l in L]) // if pieces >= k : // start = mid // else : // end = mid // // if sum([l / end for l in L]) > k: // return end // return start //} #include <stdio.h> #include <numeric> using namespace std; int k(0); int array[10000]; int len(0), max_wood(0); int WoodCut()//二分查找上界 { int sum = accumulate(array, array+len,0); if (sum < k) return 0; int left(1), right(max_wood); int mid; while (left+1<right) { mid = left + (right - left) / 2; int k_tmp(0); for (auto i = 0; i <= len ;i++) { k_tmp += array[i] / mid; } if (k_tmp>=k) { left = mid; } else { right = mid; } } int right_k(0); for (auto i = 0; i <= len; i++) { right_k += array[i] / right; } if (right_k>=k) { return right; } else { return left; } return 0; } int main() { char c; scanf("%d", &k); while (1) { scanf("%d", &array[len]); if (array[len]>max_wood ) { max_wood = array[len]; } c = getchar(); if (c=='\n') { break; } ++len; } printf("%d",WoodCut()); return 1; }讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/28210.html