A8028木材加工——题解

题意要求我们把木材切割成很多段，使得这个短段尽量的长。

我们切割的段肯定是在[ 0,max{ wood [ i ] } ]中，满足二分的有界性。

由题意显然单调，满足单调性。所以可以使用二分答案求解。

如果发现能切够k段则去右半部分找更大的解，如果发现切不够k段就去左边找可行解。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[1000005];
bool ef(int x){
	int sum=0;
	for(int i=1;i<=n;++i){
		sum+=a[i]/x;
	}
	return sum>=k;
}
int main(){
	cin>>n>>k;
	int maxx=INT_MIN;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		maxx=max(maxx,a[i]);
	}
	int l=0;
	int r=maxx+1;
	while(l+1<r){
		int mid=(l+r)/2;
		if(ef(mid)){
			l=mid;
		}
		else
		{
			r=mid;
		}
	}
	cout<<l;
	return 0;
}