时间复杂度
O(nlogm),有n条绳子,m是绳子中长度最长的一条的长度
思路
浮点数二分
将一个最优化问题,转换为一个判定问题。然后用二分去逼近满足判定条件的最优结果。
代码
```c++
# include <iostream>
using namespace std;
const int N = 1e6+10;
int n, m;
int L[N];
//注意,为保证精度,输入的是double,不是float
int check(double x){
int res = 0;
for(int i = 0; i<n; i++){
res += L[i]/x;
}
//printf("%d ", res);
if (res >= m) return 1;
else return 0;
}
int main(){
double l, r, mid;
l = 0;
r = 1e9;
cin >> n >> m;
for (int i = 0; i < n; i++){
cin >> L[i];
}
while(r-l >1e-4){
mid = (l+r)/2;
//printf("%.2f\n", mid);
if (check(mid)==1){
l = mid;
}
else{
r = mid;
}
}
printf("%.2f\n", l);
return 0;
}
```