POJ 2976 Dropping tests

In a certain course, you take n tests. If you get a_i out of b_i 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 .

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 a_i for all i. The third line contains npositive integers indicating b_i for all i. It is guaranteed that 0 ≤ a_i ≤ b_i ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

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.

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

题目大意就 给定n个二元组(a,b)，扔掉k个二元组，使得剩下的a元素之和与b元素之和的比率最大，以下 是复制自其它人的博客

     题目求的是 max(∑a[i] * x[i] / (b[i] * x[i]))   其中a,b都是一一对应的。 x[i]取0,1  并且 ∑x[i] = n - k;

    转：那么可以转化一下。  令r = ∑a[i] * x[i] / (b[i] * x[i])  则必然∑a[i] * x[i] - ∑b[i] * x[i] * r= 0；（条件1）

并且任意的 ∑a[i] * x[i] - ∑b[i] * x[i] * max(r) <= 0  (条件2，只有当∑a[i] * x[i] / (b[i] * x[i]) = max(r) 条件2中等号才成立)

     然后就可以枚举r , 对枚举的r， 求Q(r) = ∑a[i] * x[i] - ∑b[i] * x[i] * r  的最大值，  为什么要求最大值呢？  因为我们之前知道了条件2，所以当我们枚举到r为max(r)的值时，显然对于所有的情况Q(r)都会小于等于0，并且Q(r)的最大值一定是0.而我们求最大值的目的就是寻找Q(r)=0的可能性，这样就满足了条件1，最后就是枚举使得Q(r)恰好等于0时就找到了max(r)。而如果能Q(r)&gt;0 说明该r值是偏小的，并且可能存在Q(r)=0,而Q(r)<0的话，很明显是r值偏大的，因为max(r)都是使Q(r)最大值为0，说明不可能存在Q(r)=0了。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#define eqs 1e-8
#define N 1100
using namespace std;
double a[N],b[N],c[N];
int n,k;
bool cmp(const double &p1,const double &p2)
{
    return p1<p2;
}
int main()
{
    //freopen("data.in","r",stdin);
    double binary_search(double l,double r);
    while(scanf("%d %d",&n,&k)!=EOF)
    {
        if(n==0&&k==0)
        {
            break;
        }
        for(int i=0;i<=n-1;i++)
        {
            scanf("%lf",&a[i]);
        }
        for(int i=0;i<=n-1;i++)
        {
            scanf("%lf",&b[i]);
        }
        double ans = binary_search(0,1);
        printf("%.0lf\n",ans*100);
    }
    return 0;
}
double binary_search(double l,double r)
{
    double mid;
    while(r-l>eqs)
    {
        mid = (r+l)/2;
        for(int i=0;i<=n-1;i++)
        {
            c[i] = a[i] - b[i]*mid;
        }
        sort(c,c+n,cmp);
        double sum = 0;
        for(int i=k;i<=n-1;i++)
        {
            sum+=c[i];
        }
        if(sum>0)
        {
            l = mid;
        }else
        {
            r = mid;
        }
    }
    return mid;
}