AcWing 680. 剪绳子
原题链接
简单
作者:
我要出去乱说
,
2021-01-30 10:39:36
,
所有人可见
,
阅读 388
低配版的分巧克力问题
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
double maxv;
double len[N];
bool check(double x)
{
int res = 0;
for (int i = 0; i < n; i ++ )
{
res += len[i] / x;
if (res >= m) return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ )
{
scanf("%lf", &len[i]);
maxv = max(maxv, len[i]);
}
double l = 0, r = maxv; //裁剪最后的长度范围
while (r - l > 1e-6)
{
double mid = (l + r) / 2;
if (check(mid)) l = mid; //浮点数二分不用考虑边界问题
else r = mid;
}
printf("%.2lf\n", l);
return 0;
}