POJ 2976 Dropping tests [二分]

1.题意：同poj3111，给出一组N个有价值a，重量b的物品，问去除K个之后，剩下的物品的平均值最大能取到多少？

2.分析：二分平均值，注意是去除K个，也就是选取N-K个

3.代码：

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cmath>
 4 # include <algorithm>
 5 using namespace std;
 6 const int MAXN=1005;
 7 const double eps=1e-8;
 8 int N,K;
 9 int sgn(double x)
10 {
11     if(fabs(x)<eps) return 0;
12     if(x<0) return -1;
13     else return 1;
14 }
15 struct Test
16 {
17     double a,b;
18     Test(){}
19     Test(double aa,double bb)
20     {
21         a=aa;
22         b=bb;
23     }
24 }T[MAXN];
25 void Init()
26 {
27     for(int i=0;i<N;i++)
28         scanf("%lf",&T[i].a);
29     for(int i=0;i<N;i++)
30         scanf("%lf",&T[i].b);
31 }
32 void Solve()
33 {
34     double temp[MAXN];
35     double sum;
36     double l=0.0;
37     double r=2.0;
38     while(sgn(r-l)!=0)
39     {
40         double mid=l+(r-l)/2.0;
41         for(int i=0;i<N;i++)
42             temp[i]=mid*T[i].b-T[i].a;
43         sort(temp,temp+N);    
44         sum=0;
45         for(int i=0;i<N-K;i++)
46             sum+=-temp[i];
47         //printf("%lf %lf
",mid,sum);
48         if(sgn(sum)<0) r=mid;
49         else l=mid;
50     }
51     printf("%0.f
",100.0*l);
52 }
53 int main()
54 {
55     while(scanf("%d%d",&N,&K)!=EOF)
56     {
57         if(N==0&&K==0) break;
58         Init();
59         Solve();
60     }
61     return 0;
62 }