python/TangDou/AcWing/MinusCircle/POJ2976.cpp

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int n, k;
int a[N], b[N];
const double eps = 1e-8;

double d[N];

bool check(double x) {
    for (int i = 0; i < n; i++) d[i] = a[i] - x * b[i];
    sort(d, d + n, greater<double>()); //由大到小排序

    double sum = 0;
    for (int i = 0; i < n - k; i++) sum += d[i];
    return sum >= 0; //从大到小选n-k个，看ans是否为可行的解
}

int main() {
    while (cin >> n >> k && (n || k)) {
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];

        //浮点数二分
        double l = 0, r = INF;
        while (r - l > eps) {
            double mid = (l + r) / 2; //注意浮点数不能用右移操作
            if (check(mid))
                l = mid; //向右逼近，使结果更大一些
            else
                r = mid; //向左逼近，使结果更小一些
        }
        printf("%.0lf\n", l * 100); // 四舍五入
    }
    return 0;
}