题解
使用浮点数二分法即可,二分得到中点后进行检查,如果满足能切出大于等于m根的绳子,那就让左边界等于该重点值,否则右边界等于该中点値。设置一个二分精度,当fabs(r - l) < 1e-4
时我们可以认为得到答案。
一般保留n位小数我们可以将精度设置为1e-(n+2)
,最好使用fabs,防止出现计算时浮点误差导致负数的情况。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const double EPS = 1e-4;
int n, m;
int arr[N];
bool check(double num) {
int res = 0;
for(int i = 0; i < n; i++) {
res += arr[i] / num;;
if(res >= m) return true;
}
return false;
}
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> arr[i];
double l = 0, r = 1e9;
while(fabs(r - l) > EPS) {
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
cout << fixed << setprecision(2) << l << endl;
return 0;
}