二分答案刷题2

题目来源：木材加工 - 洛谷

这道题和之前发表过的一篇文章的解题思路是一样的。迷路的小伙伴可以看下之前的一期二分答案刷题-CSDN博客，二分答案适合求解最值的问题，并且需要满足单调性的思想，从这道题可以看出，若l是把这些木头切割成k段的最大值，则增加l的值，则切割不到k段，减少l的值，不满足其最大值，符合单调性。

解题描述：

?1、check 函数：这个函数用来检查是否能从原木中至少切割出 k 段长度为 length 的木材。它通过计算所有原木可以切割出的木材段数 tol，并将其与 k 比较来实现。如果 tol 大于或等于 k，则返回 true。

?2、main 函数：主要讲下二分搜索。需要注意的是，设置二分搜索的初始边界时，left 设置为?1，是为了避免除0操作。然后while循环调用 check 函数来确定是否可以切割出足够的木材段。如果可以，则更新 ans 为 mid，并将 left 设置为 mid+1 以寻找更长的可能长度；否则，将 right 设置为 mid-1 以减小搜索范围。

代码如下：

#include<iostream>
#include<algorithm>
#define maxn 1000010 
int L[maxn], n, k;
using namespace std;

bool check(int length)
{
	long long tol = 0;
	for (int i = 0; i < n; i++)
	{
		tol += L[i] / length;  //注意防止除0

	}
	return tol >= k;
}

int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> L[i];
	}
	int left = 1, right = 1e8+1, mid, ans=0;//left从1开始是为了放置除0操作
	while (left <= right)
	{
		mid = left + (right - left) / 2;
		if (mid == 0) ans = 0;
		if (check(mid))
		{
			ans = mid;
			left = mid+1;
		}
		else
		{
			right = mid - 1;
		}
	}
	cout << ans << endl;
	return 0;
}

PS：目前对博客的创作还在摸索中，后面若遇到同类型的题目，我尽量放一块写。现在就暂时分开啦，小心食用，不喜勿喷喔。