洛谷P10505 & POJ2976 Dropping tests 题解 & 01分数规划模板

题目链接：P10505 Dropping Test

题意：

在某个课程中，你需要进行 \(n\) 次测试。

如果你在共计 \(b_i\) 道题的测试 \(i\) 上的答对题目数量为 \(a_i\)，你的累积平均成绩就被定义为 \[ 100\times \dfrac{\sum_{i=1}^n a_i}{\sum_{i=1}^n b_i} \] 给定您的考试成绩和一个正整数 \(k\)，如果您被允许放弃任何 \(k\) 门考试成绩，您的累积平均成绩的可能最大值是多少。

假设您进行了 \(3\) 次测试，成绩分别为 \(5/5,0/1\) 和 \(2/6\)。

在不放弃任何测试成绩的情况下，您的累积平均成绩是 \[ 100\times \frac{5+0+2}{5+1+6} \approx 58.33 \approx 58 \] 然而，如果你放弃第三门成绩，则您的累积平均成绩就变成了 \[ 100\times \frac{5+0}{5+1}\approx 83.33\approx 83 \] 输入格式：

输入包含多组测试用例，每个测试用例包含三行。

对于每组测试用例，第一行包含两个整数 \(n\) 和 \(k\)。

第二行包含 \(n\) 个整数，表示所有的 \(a_i\)。

第三行包含 \(n\) 个整数，表示所有的 \(b_i\)。

当输入用例 \(n=k=0\) 时，表示输入终止，且该用例无需处理。

输出格式：

对于每个测试用例，输出一行结果，表示在放弃 \(k\) 门成绩的情况下，可能的累积平均成绩最大值。

结果应四舍五入到最接近的整数。

数据范围：

\(1 \le n \le 1000\), \(0 \le k < n\), \(0 \le a_i \le b_i \le 10^9\)。

经典的 01分数规划 问题，也有称这个为分数规划的。

注意到题目要求的就是选 \(n-k\) 个物品使得 \(\sum a_i \times \dfrac{1}{\sum b_i}\) 的值尽可能的大。

不妨假设 \[ \sum a_i \times \dfrac{1}{\sum b_i} \ge x \] 移项可得 \[ \sum a_i - x \sum b_i \ge 0 \] 显然我们要求的就是 \(x\) 的最大值。考虑二分 \(x\) 的值，记 \(c_i = a_i-xb_i\) ，

每次检查只需暴力计算一下 \(c_i\) ，然后排序一下取最大的 \(n-k\) 个 \(c_i\) 算一算就好啦。

时间复杂度 \(O(-\log_2 \epsilon\cdot n \log n)\) ，取 \(\epsilon = 10^{-8}\) 就肯定够了，答案只需要四舍五入。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e3 + 15))

const double eps = 1e-8;
int n, k, a[N], b[N]; double c[N];
bool check(double x)
{
    rep(i, 1, n) c[i] = a[i] - x * b[i];
    sort(c + 1, c + 1 + n); double res = 0;
    rep(i, k + 1, n) res += c[i];
    return res >= 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(0);
    while(cin >> n >> k && n > 0)
    {
        rep(i, 1, n) cin >> a[i];
        rep(i, 1, n) cin >> b[i];
        double l = 0, r = 1;
        while(abs(r - l) >= eps)
        {
            double mid = (l + r) / 2.0;
            check(mid) ? l = mid : r = mid;
        }
        cout << l * 100 << '\n';
    }
    return 0;
}