浮点数二分 $O(nlogn)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, m;
int a[N];

bool check(double x){
    int cnt = 0;
    for (int i = 0; i < n; i ++ ){
        cnt += a[i] / x;
    }
    return cnt >= m;
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ){
        scanf("%d", &a[i]);
    }

    double l = 0, r = 1e9;
    // 1e7 / O(check函数的时间复杂度)
    // for (int i = 0; i < 100; i ++ )
    while (r - l > 1e-4){
        double mid = (r + l) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2lf", r);
    return 0;
}