P2440 木材加工【二分答案】

例题

• 二分答案
• 思路

首先我们输入 n 和 k 并且运用二分找到合适的尺寸，而l 必须要足够小，r 必须要足够的大。题中写道数组中的数最大不会超过 100000000 ，所以我们设1e8+10就可以了。

现在就走到了判断的环节，我们如何判断 mid 是太小还是太大呢？我们需要编写一个新函数 check（）。

在函数 check（） 中，我们依次要判断 a 中的每一个数并计算出能切出多少个 mid ，还要用一个变量 ans 储存他们，如果 ans 分的分数比 k 多或者正好等于，返回真。如果是小于 k ，返回假。

当 check（） 返回的是真的时候，我们就要试试还能不能把 mid 调大一点，就要

l = mid;

如果返回的是假，我们就加的太大了，就要把mid调小一点，就要

r = mid;

• A了 88 分的代码 少考虑了一个特殊情况

• AC代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long 
#define INF 0x3f3f3f3f3f
const int N = 100010;
using namespace std;
int arr[N];
int n, k;

bool check(int mid){
	int cnt = 0 ;
	for(int i = 1 ;i <= n;i++){
		cnt += arr[i]/mid;
	}
	if(cnt >= k)//数量多 咱们就把单位长度变大
		return true;
	return false;//否则...
}

signed main() {
	cin>>n>>k;
	for(int i = 1 ; i <= n;i++ ){
		cin>>arr[i];
	}
	int l = 0,r = 1e8+10;
	while(l+1<r){
		int mid = (l + r)/2;
		if(check(mid)){
			l = mid ;//单位长度变大
		}else
			r = mid;
	}
+	if(check(r)) //特殊情况
+		cout<<r;
+	else
+		cout<<l;
    return 0;
}