实数二分

为了保证四舍五入正确，多保留几位小数

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k;
int a[1005], b[1005];
double temp[1005];
bool check(double mid)
{
    // 检查选择 n-k 个能否达到 mid 分
    //  100 * (x1+x2+x3...)/(y1+y2+y3...) >= mid
    //  (100*x1-mid*y1)+(100*x2-mid*y2)+... >= 0
    for (int i = 1; i <= n; i++)
        temp[i] = 100 * a[i] - mid * b[i];
    sort(temp + 1, temp + n + 1);
    double sum = 0;
    for (int i = k + 1; i <= n; i++)
        sum += temp[i];
    return sum >= 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n >> k)
    {
        if (n == 0 && k == 0)
            break;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            cin >> b[i];
        double l = 0;
        double r = 100;
        while (r - l > 0.0001)
        {
            double mid = (l + r) / 2;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }
        cout << fixed << setprecision(0) << l << "\n";
    }
    return 0;
}

整数二分

按 1000 分算，就多一位了

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k;
int a[1005], b[1005];
int temp[1005];
bool check(int mid)
{
    // 检查选择 n-k 个能否达到 mid 分
    //  1000 * (x1+x2+x3...)/(y1+y2+y3...) >= mid
    //  (1000*x1-mid*y1)+(1000*x2-mid*y2)+... >= 0
    for (int i = 1; i <= n; i++)
        temp[i] = 1000 * a[i] - mid * b[i];
    sort(temp + 1, temp + n + 1);
    int sum = 0;
    for (int i = k + 1; i <= n; i++)
        sum += temp[i];
    return sum >= 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n >> k)
    {
        if (n == 0 && k == 0)
            break;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            cin >> b[i];
        int l = 0;
        int r = 1000;
        int ans;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (check(mid))
            {
                l = mid + 1;
                ans = mid;
            }
            else
                r = mid - 1;
        }
        cout << (ans + 5) / 10 << "\n";
    }
    return 0;
}