POJ2976基础01分数规划

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.

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二分规划的意思是对于某个数，0，1表示选择与否

AC代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#define eps 1e-8
#define maxn 10000
using namespace std;
int main()
{
    double a[maxn],b[maxn],c[maxn];//后面mid为double型的 ，最好把所有有可能的地方都换成double的
    int n,i,j,k;
    while(scanf("%d%d",&n,&k)&&(n!=0||k!=0))
    {
        for(i=0;i<n;i++)
            scanf("%lf",&a[i]);
        for(i=0;i<n;i++)
            scanf("%lf",&b[i]);
        double l=0,r=1000;//左右边界，r开的稍微大一点也没关系
        double mid;
        while(r-l>eps)//即对于浮点数的比较，r>l+eps,即r>l，所以break时r=l
        {
            mid=(r+l)/2;
            for(i=0;i<n;i++)
                c[i]=a[i]*100-mid*b[i];
            sort(c,c+n);
            double maxf=0;
            for(i=n-1;i>=k;i--)
                maxf+=c[I];//求最大，即比较删掉前面k个小的c[i]之后剩下数的和是否大于0，二分
            if(maxf>eps) l=mid;
            else r=mid;
        }
        printf("%.0lf\n",l);//此处可以输出l，r，mid
    }
    return 0;
}