题目描述
有N根绳子,第i根绳子长度为Li,现在需要M根等长的绳子,你可以对N根绳子进行任意裁剪(不能拼接),请你帮忙计算出这M根绳子最长的长度是多少。
样例
输入样例:
3 4
3 5 4
输出样例:
2.50
算法1
(浮点数二分) $O(nlogn)$
模板题
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
double eps = 1e-4;
int a[N], n, m;
bool check(double mid){
int cnt = 0;
for (int i = 0; i < n; i ++)
cnt += a[i] / mid;
return cnt >= m;
}
int main(){
cin >> n >> m;
for (int i = 0; i < n ; i++) cin >> a[i];
double l = 0, r = 1e9;
while (r - l >= eps){
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n", r);
return 0;
}