思路
为了找到满足切割数量的最大长度,我们必须要判断在区间[0, 1e9]的所有可能结果,对任意可能长度,判断是否满足题意;
如何判断长度len是否满足题意:将每一段原木按长度len切割,然后把每个原木所能切割的长度为len的段个数相加,看是否大于等于m;
采用二分搜索的方法不断缩小解空间,因为题目要求保留两位小数,所以当解空间长度小于0.001时,不会对最后的结果产生影响;
时间复杂度
C++ 代码
#include <iostream>
using namespace std;
const int maxn = 100000;
int a[maxn];
int n = 0, m = 0;//n是原来的绳子数量, m是需要的绳子数量
bool check(double mid){
int res = 0;
for(int i = 0; i < n; i ++){
res += a[i] / mid;
if(res >= m) return true;
}
return false;
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i ++) cin >> a[i];
double l = 0, r = 1e9;
while(r - l > 1e-3){
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.2f\n", l);
return 0;
}