（POJ 2976）Dropping tests（01分数规划）

Dropping tests

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 15100		Accepted: 5274

Description

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 .

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 a_i for all i. The third line contains n positive 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.

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.

Sample Input

Sample Output

83
100

Hint

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).

这是一道01分数规划的入门题目

题意就是给你n个ai，n个bi，从中选出n-k个ai和对应的bi，使得（∑ai/∑bi）取到最大值。

那我们设x=（∑ai/∑bi）；

当x取最大值时有∑ai-x*∑bi=0；

设f（t）=∑ai-x*∑bi；

所以x取最大值时f（t）=0；

因为∑bi恒大于0，所以当存在x'>x时，f（t）=∑ai-x'*∑bi<0

　　　　　　　　　　　存在x'<x时，f（t）=∑ai-x'*∑bi>0

　　　　　　　　　　　存在x'=x时，f（t）=∑ai-x'*∑bi=0

从而可以知道f（t）是一个单调递减的函数，因为它是单调函数，所以我们可以使用二分解决

二分x值，那么x的左右区间该如何确定呢？

因为x=∑ai/∑bi,我们先来考虑两项相加的情况，即（a+c）/（b+d）；

当a/b>c/d，若（a+c）/（b+d）<a/b,则ab+ac<ab+ad。即ac<ad。

因为a/b>c/d,所以ad>bc，相矛盾。

同理可证（a+c）/（b+d）>c/d。

所以可知两个这样的数依此相加，大小一定位于两者之间。

所以将每个ai/bi算出来排序，取最小值和最大值就是x的二分区间；

对于二分出来的每一个mid值，计算出每个ai-mid*bi然后排序。

注意因为题目要求的是分数越高越好，所以取最大的前n-k个值，如果这样取得的最大值小于0，说明此时mid>x，r=mid；

否则x有可能比mid大，l=mid；

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f

using namespace std;

double a[1010];
double b[1010];
int n;
int k;

bool check(double mid)
{
    double c[1010];
    for(int i=1;i<=n;i++)
    {
        c[i]=a[i]-mid*b[i];
    }
    sort(c+1,c+n+1);
    double sum=0;
    for(int j=0;j<k;j++)
        sum+=c[n-j];
    return sum>=0;
}

int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        if(n==0&&k==0)
            break;
        k=n-k;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=1;i<=n;i++)
            scanf("%lf",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%lf",&b[i]);
        double r=0;
        double l=inf;
        for(int i=1;i<=n;i++)
        {
            r=max(r,a[i]/b[i]);
            l=min(l,a[i]/b[i]);
        }
        while(r-l>0.0001)
        {
            double mid=(l+r)/2;
            if(check(mid))
                l=mid;
            else
                r=mid;
        }
        printf("%.0lf
",100*r);
    }
    return 0;
}

此地非逐弃者之王座，彼方乃行愿者之归所。无限清澈，星界银波。