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 n-k n−k 个物品使得
∑ a i × 1 ∑ b i sum a_i times dfrac{1}{sum b_i} ∑ai​×∑bi​1​
尽可能的大

不妨假设
∑ a i × 1 ∑ b i ≥ x sum a_i times dfrac{1}{sum b_i} ge x ∑ai​×∑bi​1​≥x
移项可得
∑ a i − x ∑ b i ≥ 0 sum a_i - x sum b_i ge 0 ∑ai​−x∑bi​≥0
于是可以二分一个 x x x

每次暴力检验 p s [ i ] = a i − x b i ps[i] = a_i - xb_i ps[i]=ai​−xbi​

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

时间复杂度 O ( log ⁡ 2 1 0 6 × Q n log ⁡ n ) O(log_2 10^6 times Q n log n) O(log2​106×Qnlogn)

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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;
}

转载请说明出处