考点
浮点数二分
同类题型
- AcWing 790. 数的三次方根
- 整数二分
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int w[N];
bool check(double mid)
{
int cnt = 0;//cnt表示一共可以切出来多少条长度为mid的绳子
for (int i = 0; i < n; i ++)
cnt += w[i] / mid; //cnt是每条绳子长度除以mid下取整后相加的值
return cnt >= m;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> w[i];
double l = 0, r = 1e9;
for (int i = 0; i < 100; i ++ )
{
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n", r);//这里输入r或者l都可以,因为此时r和l已经非常接近,可以认为是一个数
return 0;
}