AcWing 680. 剪绳子
原题链接
简单
作者:
uuuzi
,
2021-04-26 10:21:24
,
所有人可见
,
阅读 378
欢迎点赞
#include<iostream>
using namespace std;
const int N = 1e5 +10;
int a[N];
int n,m;
bool check(double len){
int res =0 ;
for(int i = 0;i < n;i++){
res += a[i] / len; // 求能剪出多少根绳子,把每根绳子的长度除以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 )//小数二分r - l要大于1e-3{
double mid = (l + r) / 2.0;
if(check(mid)) l = mid;//绳子可以剪出比mid长的可能
else r =mid; // 否则缩小区域
}
printf("%.2lf",l);
return 0;
}