AcWing 680. 剪绳子
原题链接
简单
作者:
acw_yxy
,
2021-01-14 13:15:53
,
所有人可见
,
阅读 261
算法1
(二分法)
C++ 代码(借鉴第一个题解哈哈哈)
#include <iostream>
#include <iomanip>
using namespace std;
const int N = 100010;
int n, m;
double l[N];
bool check(double x)
{
int res = 0;
for(int i = 0; i < n; i ++)
res += l[i] / x; // 直接舍去小数部分
if(res >= m) return true;
return false;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i ++)
cin >> l[i];
double l = 0, r = 1e9;
while(r - l > 1e-3)
{
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
cout << fixed << setprecision(2) << l;
return 0;
}