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

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

思路：

为了做POJ 2728 ，先做此题，作为练习。

此题有一个算法，叫做01分数规划，目标就是求给定条件下的平均值最大值。平均值最大值是不可以直接有各个平均值累和的，这是因为S(a)/S(b）----s表示求和，这个式子就是平均值。

对于这个式子，很明显是除法运算，所以S(a)/S(b)并不会等于S(a/b),这是显而易见的，而我们现在要做的就是，找出这样一个x，使得S(a)/S(b)与x作比较，并对x进行调整，直到找出满足条件的临界点为止。此时，为了方便计算，我们可以做一点变形，就是S(a)与S(b)*x比较，在这种情况下，我们就可以求出每一点的a-b*x，再进行累和了，因为现在是减法运算。

代码

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 using namespace std;

 typedef long long ll;

 ll a[],b[];

 int n,k;

 const double eps = 1e-;

 double ans[];

 double num(double m)

 {

     for(int i=;i<=n;i++){

         ans[i]=a[i]-m*b[i];

     }

     sort(ans+,ans++n);

     double sum=;

     for(int i=n;i>=k+;i--){sum+=ans[i];}

     return sum>=;

 }

 int main()

 {

     while(scanf("%d%d",&n,&k)!=EOF&&n+k){

         for(int i=;i<=n;i++){

             scanf("%lld",&a[i]);

         }

         for(int i=;i<=n;i++){

             scanf("%lld",&b[i]);

         }

         double mid,l,r;

         l=,r=;

         while(r-l>eps){

             mid=(l+r)/;

             if(num(mid)){l=mid;}

             else r=mid;

         }

         printf("%.0f\n",mid*);

     }

 }