【题目来源】
洛谷：P2440 木材加工 - 洛谷
【题目描述】
木材厂有 \(n\) 根原木，现在想把这些木头切割成 \(k\) 段长度均为 \(l\) 的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出 \(l\) 的最大值。
木头长度的单位是 \(cm\)，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 \(11\) 和 \(21\)，要求切割成等长的 \(6\) 段，很明显能切割出来的小段木头长度最长为 \(5\)。
【输入】
第一行是两个正整数 \(n,k\)，分别表示原木的数量，需要得到的小段的数量。
接下来 \(n\) 行，每行一个正整数 \(L_i\)，表示一根原木的长度。
【输出】
仅一行，即 \(l\) 的最大值。
如果连 \(1cm\) 长的小段都切不出来，输出 0。
【输入样例】
3 7
232
124
456
【输出样例】
114
【解题思路】
【算法标签】
《洛谷 P2440 木材加工》 #贪心# #线性数据结构# #二分# #递归#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n: 绳子数量
// k: 需要切割的段数
// a[100005]: 存储每根绳子的长度
int n, k, a[100005];int main()
{// 输入绳子数量n和需要切割的段数kcin >> n >> k;// 输入每根绳子的长度for (int i = 0; i < n; i++){cin >> a[i];}// 初始化二分查找的左右边界int l = 0, r = 1e8;// 二分查找最大可能的切割长度while (l <= r && r != 0){int tmp = 0; // 记录当前切割长度下能得到的段数int mid = l + (r - l) / 2; // 计算中间值，防止溢出// 计算所有绳子按mid长度切割能得到的段数总和for (int i = 0; i < n; i++){tmp += a[i] / mid;}// 根据计算结果调整搜索范围if (tmp >= k){l = mid + 1; // 可以切割更长，向右搜索}else if (tmp < k){r = mid - 1; // 需要切割更短，向左搜索}}// 输出最终确定的最大切割长度cout << r << endl;return 0;
}
【运行结果】
3 7
232
124
456
114