Algorithm6.1 贪心 VS 其他算法

#include <iostream>
using namespace std;
const int maxn = 205;
int n, m, a[maxn], b[maxn];
double l, mid, r;
#include <algorithm>

double check(double x) {
    double w[maxn];
    for (int i = 1; i <= n; ++i) w[i] = b[i]*x-a[i];
    sort(w+1, w+1+n);
    double tmp = 0;
    for (int i = 1; i <= m; ++i) tmp += w[i];
    return tmp;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a+i);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", b+i);
        r = max(r, a[i]*1.0/b[i]);
    }
    while (l < r && abs(r-l) > 1e-5) {
        mid = (l+r)/2;
        if (check(mid) == 0) break;
        else if (check(mid) < 0) l = mid;
        else r = mid;
    }
    printf("%.3lf\n", mid);
    return 0;
}