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
.
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.
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.
y=100*sigma(ai)/sigma(bi)
t(y)=100*sigma(ai)-y*sigma(bi)
问最后去掉那几个k能得到正好的值，
***************************************************************************************************************************
1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<queue> 7 #include<algorithm> 8 using namespace std; 9 double a[1001],b[1001],score[1001]; 10 int n,k,i,j; 11 const double eps=1e-8; 12 int main() 13 { 14 while(scanf("%d %d",&n,&k)&&(n+k)) 15 { 16 for(i=0;i<n;i++) 17 scanf("%lf",&a[i]); 18 for(i=0;i<n;i++) 19 scanf("%lf",&b[i]); 20 double le=0,ri=100,mid,sum; 21 while(ri-le>eps) 22 { 23 mid=(ri+le)/2; 24 for(i=0;i<n;i++) 25 score[i]=100*a[i]-b[i]*mid; 26 sort(score,score+n); 27 sum=0; 28 for(i=k;i<n;i++) 29 sum+=score[i]; 30 if(sum>0) 31 le=mid; 32 else 33 ri=mid; 34 } 35 printf("%.0f\n",le); 36 } 37 return 0; 38 }