P4377 [USACO18OPEN] Talent Show G

P4377 [USACO18OPEN] Talent Show G

比值问题，分数规划，先推式子。
$$
\begin {array}
& \frac {\sum _ {i = 1} ^ n w _ i} {\sum _ {i = 1} ^ n v _ i} \ge mid \\
\sum _ {i = 1} ^ n w _ i \ge mid \sum _ {i = 1} ^ n v _ i \\
\sum _ {i = 1} ^ n w _ i - mid \times v _ i \ge 0
\end {array}
$$

要求 $V$ 满足最小值，大于 $V$ 时就存在 $V$ 即可。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 260, M = 1e3 + 10;
const double eps = 1e-5, inf = 1e9;
int n, V, v[N], w[N];
double f[M];
bool check(double mid)
{
    for (int i = 0; i <= V; i++)
        f[i] = -inf;
    f[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= 0; j--)
            f[min(V, j + v[i])] = max(f[min(V, j + v[i])], f[j] + w[i] - mid * v[i]);
    return f[V] > -eps;
}
int main()
{
    scanf("%d%d", &n, &V);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    double l = 0, r = 25e4;
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%d", (int)(l * 1000));
    return 0;
}