POJ2976 Dropping tests 题解

题目链接：POJ2976 Dropping tests

题意：

Description

In a certain course, you take n tests. If you get ai out of bi questions correct on test i, your cumulative average is defined to be

.

Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.

Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .

Input

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ ai ≤ bi ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

Output

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

经典的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$

每次暴力检验 $ps[i] = a_i - xb_i$

注意要排个序然后取最大的 $n-k$ 个 $ps[i]$

时间复杂度 $O(\log_2 10^6 \times Q n \log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)
const double eps=1e-13;
int n,k,a[N],b[N];
double ps[N];
bool ck(double x)
{
    for(int i=1; i<=n; i++)
        ps[i]=a[i]-x*b[i];
    sort(ps+1,ps+1+n);
    double res=0;
    for(int i=k+1; i<=n; i++)
        res+=ps[i];
    return res>=0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cout << fixed << setprecision(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(cin >> n >> k && n)
    {
        for(int i=1; i<=n; i++) cin >> a[i];
        for(int i=1; i<=n; i++) cin >> b[i];
        double l=0,r=1;
        while(r-l>1e-6)
        {
            double mid=(l+r)/2;
            if(ck(mid))l=mid;
            else r=mid;
        }
        cout << l*100 << endl;
    }

    return 0;
}