题解 | #wyh的物品#

01分数规划的浮点数二分

经典01分数规划，当前物体的价值和重量是v和w。选取k个物品，使得总体的单位价值最大

二分可能的最终单位价值做check，check选取的最大值符合一个等式：

$\frac{sum(v_i)}{sum(w_i)}>=mid\backslash frac\{sum(v\_i)\}\{sum(w\_i)\}\; >=\; mid$

变形一下：

$sum(v_i)-sum(w_i)\ast mid>=0sum(v\_i)\; -\; sum(w\_i)\; *\; mid\; >=\; 0$

针对每一个物品：

$d_i=v_i-mid\ast w_i>=0d\_i\; =\; v\_i\; -\; mid\; *\; w\_i\; >=\; 0$

只要选取的k个最大的$d_{i}d\_i$，其和 >= 0 就是合法解

因此不难推得一个最大值的通式：

$\frac{sum(a_i\ast w_i)}{sum(b_i\ast w_i)}>mid\backslash frac\{sum(a\_i\; *\; w\_i)\}\{sum(b\_i\; *\; w\_i)\}\; >\; mid$

$sum(a_i\ast w_i)-sum(b_i\ast w_i)\ast mid>0sum(a\_i\; *\; w\_i)\; -\; sum(b\_i\; *\; w\_i)\; *\; mid\; >\; 0$

$sum(w_i\ast (a_i-mid\ast b_i))>0sum(w\_i\; *\; (a\_i\; -\; mid\; *\; b\_i))\; >\; 0$

Code

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

// Created by Simonhancrew on 2022/04/29

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define fast_cin()                    \
    ios_base::sync_with_stdio(false); \
    cin.tie(nullptr);                 \
    cout.tie(nullptr)

#define x first
#define y second

const int INF = 0x3f3f3f3f, N = 1e6 + 10;

using PDD = pair<double, double>;
const double eps = 1e-6;

PDD p[N];
double d[N];
int n, k;

bool check(double mid)
{
    for (int i = 0; i < n; i++)
    {
        d[i] = p[i].y - p[i].x * mid;
    }
    sort(d, d + n, [](double l, double r)
         { return l > r; });
    double sum = 0;
    for (int i = 0; i < k; i++)
    {
        sum += d[i];
    }
    return sum >= 0;
}

int main()
{
    fast_cin();
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        for (int i = 0; i < n; i++)
            cin >> p[i].x >> p[i].y;
        double l = 0, r = 1e6;
        while (r - l > eps)
        {
            double mid = (r + l) / 2;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }
        printf("%.2f\n", l);
    }
    return 0;
}