题解 洛谷 Luogu P2440 木材加工 二分答案 C/C++
题目传送门：
P2440 木材加工 - 洛谷 | 计算机科学教育新生态
https://www.luogu.com.cn/problem/P2440思路
很简单的二分答案
每次找区间中点 m，判断每段长度为 m 时木头段总数是否 >= k 即可
有两个细节需要注意一下
1.left 初始值应为 1 而非 0，否则有可能出现除以 0 的情况 (没错，我 RE 了 2 个点才想起来)
2.一开始我是把 r 设定为 arr[i] 最小值的，这样 AC 了 6/8 的测试点
为什么会剩 2 个点 WA 呢，因为有这样的数据：n = 3, k = 2, arr = { 1, 3, 3 }
要分成 2 段木头，易知答案为 3。这种情况下 r 设定为 arr[i] 最小值就不对了
因为有些短木头连一段都算不上，直接被舍弃了
所以 r 应设定为 arr[i] 最大值
代码：
#include <cstdio>
using namespace std;
const int N = 1E5 + 10;
int arr[N], n, k, l = 1, r, m, ans;
{
int ret = 0;
for (int i = 0; i < n; i++)
{
ret += arr[i] / m;
if (ret >= k) return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
if (arr[i] > r) r = arr[i];
}
while (l <= r)
{
m = l + r >> 1;
if (mp(m)) ans = m, l = m + 1;
else r = m - 1;
}
printf("%d", ans);//ans 一次都没更新过的话就是 0，符合题目要求
return 0;
}